100 lines
2.5 KiB
C++
100 lines
2.5 KiB
C++
#include <iostream>
|
|
#include <map>
|
|
#include <set>
|
|
#include <string>
|
|
#include <vector>
|
|
|
|
using Int = unsigned;
|
|
using Coord = std::pair<Int, Int>;
|
|
using Map = std::vector<std::string>;
|
|
using PointMap = std::map<char, Coord>;
|
|
using PointCostMap = std::multimap<char, std::pair<char, Int>>;
|
|
|
|
void update_cost_map(PointCostMap& cost_map, Map const& map, std::pair<char, Coord> start)
|
|
{
|
|
std::set<Coord> visited;
|
|
std::set<Coord> to_visit;
|
|
to_visit.insert(start.second);
|
|
|
|
Int cost{0};
|
|
while (!to_visit.empty()) {
|
|
visited.insert(to_visit.begin(), to_visit.end());
|
|
std::set<Coord> next_to_visit;
|
|
for (auto const& n : to_visit) {
|
|
char c{map[n.second][n.first]};
|
|
if (c == '#') {
|
|
abort();
|
|
}
|
|
|
|
if (c != '.') {
|
|
cost_map.insert({start.first, {c, cost}});
|
|
}
|
|
|
|
auto add = [&map, &visited, &next_to_visit](Int x, Int y) {
|
|
if (map[y][x] != '#' && !visited.contains(Coord{x, y})) {
|
|
next_to_visit.insert(Coord{x, y});
|
|
}
|
|
};
|
|
add(n.first, n.second - 1);
|
|
add(n.first, n.second + 1);
|
|
add(n.first - 1, n.second);
|
|
add(n.first + 1, n.second);
|
|
}
|
|
++cost;
|
|
std::swap(to_visit, next_to_visit);
|
|
}
|
|
}
|
|
|
|
auto find_lowest_cost(PointCostMap const& cost_map, std::size_t point_count)
|
|
-> std::pair<std::string, Int>
|
|
{
|
|
std::multimap<Int, std::string> nodes;
|
|
nodes.insert({0, "0"});
|
|
|
|
while (!nodes.empty()) {
|
|
auto it{nodes.begin()};
|
|
Int cost{it->first};
|
|
std::string visited{it->second};
|
|
if (visited.size() == point_count) {
|
|
return {visited, cost};
|
|
}
|
|
nodes.erase(it);
|
|
|
|
auto [cm_begin, cm_end] = cost_map.equal_range(visited[visited.size() - 1]);
|
|
for (auto cm_it{cm_begin}; cm_it != cm_end; ++cm_it) {
|
|
if (visited.find(cm_it->second.first) == std::string::npos) {
|
|
nodes.insert({cost + cm_it->second.second, visited + cm_it->second.first});
|
|
}
|
|
}
|
|
}
|
|
|
|
abort();
|
|
}
|
|
|
|
auto main() -> int
|
|
{
|
|
Map map;
|
|
PointMap points;
|
|
std::string line;
|
|
|
|
// Read in map and find the locations we want to visit.
|
|
while (std::getline(std::cin, line) && !line.empty()) {
|
|
auto y{map.size()};
|
|
map.push_back(line);
|
|
std::size_t x{0};
|
|
for (x = line.find_first_not_of(".#", x); x != std::string::npos;
|
|
x = line.find_first_not_of(".#", x + 1)) {
|
|
points.insert({line[x], {x, y}});
|
|
}
|
|
}
|
|
|
|
PointCostMap cost_map;
|
|
for (auto const& p : points) {
|
|
update_cost_map(cost_map, map, p);
|
|
}
|
|
|
|
auto [route, cost] = find_lowest_cost(cost_map, points.size());
|
|
std::cout << "Route: " << route << " costs " << cost << '\n';
|
|
return 0;
|
|
}
|