pathfind.cpp (1847B)
1 #include <iostream> 2 #include <format> 3 #include <vector> 4 #include <deque> 5 #include <algorithm> 6 #include <set> 7 8 struct node { 9 std::string name; 10 std::vector<node*> edges; 11 }; 12 13 std::deque<node> all_stations; 14 15 void connect(node& a, node& b) 16 { 17 a.edges.push_back(&b); 18 b.edges.push_back(&a); 19 } 20 21 struct visitation 22 { 23 node* location; 24 visitation* from; 25 }; 26 27 std::vector<node*> pathfind(node& start, node& dest) 28 { 29 std::deque<visitation> candidates{{&start, nullptr}}; 30 std::deque<visitation> visited; 31 32 while (not candidates.empty()) 33 { 34 visited.emplace_back(candidates.front()); 35 candidates.pop_front(); 36 auto& visiting = visited.back(); 37 38 if (visiting.location == &dest) 39 { 40 std::vector<node*> backtrack; 41 visitation* v = &visiting; 42 do 43 backtrack.push_back(v->location); 44 while ((v = v->from)); 45 std::ranges::reverse(backtrack); 46 return backtrack; 47 } 48 49 for (auto next : visiting.location->edges) 50 if (std::ranges::none_of(visited, [next](auto const& v) { return v.location == next; })) 51 candidates.emplace_back(next, &visiting); 52 } 53 54 return {}; 55 } 56 57 int main() 58 { 59 auto& a = all_stations.emplace_back("A"); 60 auto& b = all_stations.emplace_back("B"); 61 auto& c = all_stations.emplace_back("C"); 62 auto& d = all_stations.emplace_back("D"); 63 auto& e = all_stations.emplace_back("E"); 64 auto& f = all_stations.emplace_back("F"); 65 auto& g = all_stations.emplace_back("G"); 66 all_stations.emplace_back("Unconnected"); 67 68 connect(a, b); 69 connect(b, c); 70 connect(c, d); 71 connect(d, e); 72 connect(e, f); 73 connect(f, g); 74 connect(c, e); 75 76 for (auto s : pathfind(b, f)) 77 std::cout << std::format("'{}'\n", s->name); 78 }