fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <cmath>
  5. #include <unordered_set>
  6. #include <unordered_map>
  7. #include <algorithm>
  8. #include <limits>
  9. #include <iomanip> 
  10.  
  11. using namespace std;
  12.  
  13. struct Point {
  14.     double x, y;
  15. };
  16.  
  17. struct AStarNode {
  18.     int id;
  19.     double f, g;
  20.     bool operator>(const AStarNode& other) const {
  21.         return f > other.f;
  22.     }
  23. };
  24.  
  25. unordered_map<string, int> node_ids;
  26. unordered_map<int, string> node_names;
  27. int current_id = 0;
  28.  
  29. int getId(const string& name) {
  30.     if (node_ids.find(name) == node_ids.end()) {
  31.         node_ids[name] = current_id;
  32.         node_names[current_id] = name;
  33.         current_id++;
  34.     }
  35.     return node_ids[name];
  36. }
  37.  
  38. double calculate_heuristic(int node_id, const vector<Point>& coordinates, const unordered_set<int>& exits) {
  39.     double min_dist = numeric_limits<double>::infinity();
  40.     for (int exit_id : exits) {
  41.         double dx = coordinates[node_id].x - coordinates[exit_id].x;
  42.         double dy = coordinates[node_id].y - coordinates[exit_id].y;
  43.         double feet_dist = sqrt(dx * dx + dy * dy) * 0.0729; 
  44.         if (feet_dist < min_dist) min_dist = feet_dist;
  45.     }
  46.     return min_dist;
  47. }
  48.  
  49.  
  50. vector<int> a_star_evacuation(
  51.     int start_node, 
  52.     const unordered_set<int>& exits, 
  53.     const vector<vector<pair<int, double>>>& graph, 
  54.     const vector<Point>& coordinates,
  55.     const unordered_set<int>& fire_nodes, 
  56.     double& out_distance) 
  57. {
  58.     int num_nodes = graph.size();
  59.     vector<double> g_score(num_nodes, numeric_limits<double>::infinity());
  60.     g_score[start_node] = 0.0;
  61.     vector<int> parent(num_nodes, -1);
  62.  
  63.     priority_queue<AStarNode, vector<AStarNode>, greater<AStarNode>> open_set;
  64.     open_set.push({start_node, calculate_heuristic(start_node, coordinates, exits), 0.0});
  65.  
  66.     while (!open_set.empty()) {
  67.         AStarNode current = open_set.top();
  68.         open_set.pop();
  69.         int u = current.id;
  70.  
  71.         if (exits.count(u)) {
  72.             out_distance = current.g; 
  73.             vector<int> path;
  74.             int curr = u;
  75.             while (curr != -1) {
  76.                 path.push_back(curr);
  77.                 curr = parent[curr];
  78.             }
  79.             reverse(path.begin(), path.end());
  80.             return path;
  81.         }
  82.  
  83.         if (current.g > g_score[u]) continue;
  84.  
  85.         for (const auto& edge : graph[u]) {
  86.             int v = edge.first;
  87.             double weight = edge.second;
  88.  
  89.             if (fire_nodes.count(v)) continue; 
  90.  
  91.             double tentative_g = g_score[u] + weight;
  92.  
  93.             if (tentative_g < g_score[v]) {
  94.                 parent[v] = u;
  95.                 g_score[v] = tentative_g;
  96.                 double f = tentative_g + calculate_heuristic(v, coordinates, exits);
  97.                 open_set.push({v, f, tentative_g});
  98.             }
  99.         }
  100.     }
  101.     return {}; 
  102. }
  103.  
  104. int main() {
  105.     // 1. Initialize Coordinates
  106.     vector<Point> coords_temp(38);
  107.     auto addNode = [&](string name, double x, double y) {
  108.         int id = getId(name);
  109.         coords_temp[id] = {x, y};
  110.     };
  111.  
  112.     addNode("door[0]", 638.0, 213.0); addNode("door[1]", 680.0, 1049.0);
  113.     addNode("door[2]", 1103.0, 1420.0); addNode("door[3]", 1640.0, 1626.0);
  114.     addNode("door[4]", 1635.0, 1167.0); addNode("door[5]", 2358.0, 1294.0);
  115.     addNode("door[6]", 2718.0, 1578.0); addNode("door[7]", 2651.0, 1367.0);
  116.     addNode("door[8]", 3132.0, 1179.0); addNode("door[9]", 3525.0, 1049.0);
  117.     addNode("door[10]", 3522.0, 1505.0);
  118.  
  119.     addNode("exits[0]", 638.0, 1240.0); addNode("exits[1]", 1095.0, 1917.0);
  120.     addNode("exits[2]", 2317.0, 1767.0); addNode("exits[3]", 3038.0, 959.0);
  121.  
  122.     addNode("coridor[0]", 736.0, 138.0); addNode("coridor[1]", 1220.0, 818.0);
  123.     addNode("coridor[2]", 718.0, 1182.0); addNode("coridor[3]", 884.0, 1417.0);
  124.     addNode("coridor[4]", 1032.0, 1309.0); addNode("coridor[5]", 1385.0, 1049.0);
  125.     addNode("coridor[6]", 1186.0, 1845.0); addNode("coridor[7]", 1473.0, 1169.0);
  126.     addNode("coridor[8]", 1470.0, 1045.0); addNode("coridor[9]", 1742.0, 1545.0);
  127.     addNode("coridor[10]", 1934.0, 1667.0); addNode("coridor[11]", 2320.0, 1665.0);
  128.     addNode("coridor[12]", 2433.0, 1665.0); addNode("coridor[13]", 2434.0, 1046.0);
  129.     addNode("coridor[14]", 2434.0, 1293.0); addNode("coridor[15]", 2559.0, 1049.0);
  130.     addNode("coridor[16]", 2558.0, 1368.0); addNode("coridor[17]", 2559.0, 1668.0);
  131.     addNode("coridor[18]", 2721.0, 1665.0); addNode("coridor[19]", 3523.0, 1669.0);
  132.     addNode("coridor[20]", 3038.0, 1049.0); addNode("coridor[21]", 3133.0, 1048.0);
  133.     addNode("coridor[22]", 3398.0, 1048.0);
  134.  
  135.     // 2. Build Graph
  136.     vector<vector<pair<int, double>>> graph(38);
  137.     auto addEdge = [&](string u, string v, double w) {
  138.         graph[getId(u)].push_back({getId(v), w});
  139.         graph[getId(v)].push_back({getId(u), w}); 
  140.     };
  141.  
  142.     addEdge("door[0]", "coridor[0]", 9.1); addEdge("door[0]", "door[1]", 61.02);
  143.     addEdge("door[1]", "coridor[2]", 9.95); addEdge("door[2]", "coridor[4]", 9.33);
  144.     addEdge("door[2]", "door[3]", 41.53); addEdge("door[3]", "coridor[9]", 9.52);
  145.     addEdge("door[4]", "coridor[7]", 12.02); addEdge("door[4]", "door[5]", 52.80);
  146.     addEdge("door[5]", "coridor[14]", 5.74); addEdge("door[6]", "door[7]", 15.77);
  147.     addEdge("door[6]", "coridor[18]", 6.48); addEdge("door[7]", "door[8]", 37.92);
  148.     addEdge("door[7]", "coridor[16]", 6.87); addEdge("door[8]", "coridor[21]", 9.27);
  149.     addEdge("door[9]", "door[10]", 33.09); addEdge("door[9]", "coridor[22]", 9.13);
  150.     addEdge("door[10]", "coridor[19]", 12.06);
  151.     addEdge("exits[0]", "coridor[2]", 6.84); addEdge("exits[1]", "coridor[6]", 8.39);
  152.     addEdge("exits[2]", "coridor[11]", 6.53); addEdge("exits[3]", "coridor[20]", 6.49);
  153.     addEdge("coridor[0]", "coridor[1]", 60.81); addEdge("coridor[1]", "coridor[2]", 45.29);
  154.     addEdge("coridor[1]", "coridor[5]", 20.31); addEdge("coridor[2]", "coridor[3]", 20.98);
  155.     addEdge("coridor[3]", "coridor[4]", 13.36); addEdge("coridor[3]", "coridor[6]", 38.41);
  156.     addEdge("coridor[4]", "coridor[5]", 31.51); addEdge("coridor[5]", "coridor[7]", 10.75);
  157.     addEdge("coridor[5]", "coridor[8]", 6.08); addEdge("coridor[7]", "coridor[9]", 34.22);
  158.     addEdge("coridor[8]", "coridor[13]", 70.45); addEdge("coridor[9]", "coridor[10]", 16.29);
  159.     addEdge("coridor[10]", "coridor[11]", 28.24); addEdge("coridor[11]", "coridor[12]", 8.52);
  160.     addEdge("coridor[12]", "coridor[14]", 26.64); addEdge("coridor[12]", "coridor[17]", 8.92);
  161.     addEdge("coridor[13]", "coridor[14]", 17.76); addEdge("coridor[13]", "coridor[15]", 8.88);
  162.     addEdge("coridor[15]", "coridor[16]", 23.21); addEdge("coridor[15]", "coridor[20]", 34.74);
  163.     addEdge("coridor[16]", "coridor[17]", 21.24); addEdge("coridor[17]", "coridor[18]", 11.64);
  164.     addEdge("coridor[18]", "coridor[19]", 59.08); addEdge("coridor[20]", "coridor[21]", 7.02);
  165.     addEdge("coridor[21]", "coridor[22]", 19.48);
  166.  
  167.     unordered_set<int> exit_ids = {
  168.         getId("exits[0]"), getId("exits[1]"), 
  169.         getId("exits[2]"), getId("exits[3]")
  170.     };
  171.  
  172.     vector<string> all_doors = {
  173.         "door[0]", "door[1]", "door[2]", "door[3]", "door[4]",
  174.         "door[5]", "door[6]", "door[7]", "door[8]", "door[9]", "door[10]"
  175.     };
  176.  
  177.     cout << "--- EVACUATION SYSTEM CONTROL ---\n";
  178.     cout << "Enter the number of active fire zones: ";
  179.     int num_fires;
  180.     cin >> num_fires;
  181.  
  182.     unordered_set<int> active_fires;
  183.     for (int i = 0; i < num_fires; ++i) {
  184.         string fire_location;
  185.         cout << "Enter location for Fire " << (i + 1) << " (e.g., coridor[15], door[1]): ";
  186.         cin >> fire_location;
  187.  
  188.         if (node_ids.find(fire_location) != node_ids.end()) {
  189.             active_fires.insert(getId(fire_location));
  190.         } else {
  191.             cout << "Warning: Node '" << fire_location << "' does not exist. Skipping.\n";
  192.         }
  193.     }
  194.  
  195.     cout << "\nCalculating safest routes avoiding all fire zones...\n";
  196.     cout << string(60, '=') << "\n\n";
  197.  
  198.     for (const string& door_name : all_doors) {
  199.         cout << "From " << door_name << ":\n";
  200.  
  201.         if (active_fires.count(getId(door_name))) {
  202.             cout << "  [!] THIS DOOR IS ON FIRE. EVACUATION IMPOSSIBLE.\n\n";
  203.             continue;
  204.         }
  205.  
  206.         double total_distance = 0.0;
  207.         vector<int> path = a_star_evacuation(getId(door_name), exit_ids, graph, coords_temp, active_fires, total_distance);
  208.  
  209.         if (!path.empty()) {
  210.             cout << "  Path: ";
  211.             for (int i = 0; i < path.size(); ++i) {
  212.                 cout << node_names[path[i]] << (i == path.size() - 1 ? "" : " -> ");
  213.             }
  214.  
  215.             double clear_time_sec = total_distance / 4.0;
  216.             double smoke_time_sec = total_distance / 1.5;
  217.  
  218.             cout << fixed << setprecision(2);
  219.             cout << "\n  Distance: " << total_distance << " ft";
  220.             cout << "\n  Est. Time (Clear): " << clear_time_sec << " seconds";
  221.             cout << "\n  Est. Time (Smoky): " << smoke_time_sec << " seconds\n\n";
  222.         } else {
  223.             cout << "  [!] NO SAFE ROUTE. FIRES BLOCK ALL PATHS TO EXITS.\n\n";
  224.         }
  225.     }
  226.  
  227.     return 0;
  228. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
--- EVACUATION SYSTEM CONTROL ---
Enter the number of active fire zones: Enter location for Fire 1 (e.g., coridor[15], door[1]): Warning: Node '' does not exist. Skipping.
Enter location for Fire 2 (e.g., coridor[15], door[1]): Warning: Node '' does not exist. Skipping.

Calculating safest routes avoiding all fire zones...
============================================================

From door[0]:
  Path: door[0] -> door[1] -> coridor[2] -> exits[0]
  Distance: 77.81 ft
  Est. Time (Clear): 19.45 seconds
  Est. Time (Smoky): 51.87 seconds

From door[1]:
  Path: door[1] -> coridor[2] -> exits[0]
  Distance: 16.79 ft
  Est. Time (Clear): 4.20 seconds
  Est. Time (Smoky): 11.19 seconds

From door[2]:
  Path: door[2] -> coridor[4] -> coridor[3] -> coridor[2] -> exits[0]
  Distance: 50.51 ft
  Est. Time (Clear): 12.63 seconds
  Est. Time (Smoky): 33.67 seconds

From door[3]:
  Path: door[3] -> coridor[9] -> coridor[10] -> coridor[11] -> exits[2]
  Distance: 60.58 ft
  Est. Time (Clear): 15.14 seconds
  Est. Time (Smoky): 40.39 seconds

From door[4]:
  Path: door[4] -> coridor[7] -> coridor[5] -> coridor[1] -> coridor[2] -> exits[0]
  Distance: 95.21 ft
  Est. Time (Clear): 23.80 seconds
  Est. Time (Smoky): 63.47 seconds

From door[5]:
  Path: door[5] -> coridor[14] -> coridor[12] -> coridor[11] -> exits[2]
  Distance: 47.43 ft
  Est. Time (Clear): 11.86 seconds
  Est. Time (Smoky): 31.62 seconds

From door[6]:
  Path: door[6] -> coridor[18] -> coridor[17] -> coridor[12] -> coridor[11] -> exits[2]
  Distance: 42.09 ft
  Est. Time (Clear): 10.52 seconds
  Est. Time (Smoky): 28.06 seconds

From door[7]:
  Path: door[7] -> coridor[16] -> coridor[17] -> coridor[12] -> coridor[11] -> exits[2]
  Distance: 52.08 ft
  Est. Time (Clear): 13.02 seconds
  Est. Time (Smoky): 34.72 seconds

From door[8]:
  Path: door[8] -> coridor[21] -> coridor[20] -> exits[3]
  Distance: 22.78 ft
  Est. Time (Clear): 5.70 seconds
  Est. Time (Smoky): 15.19 seconds

From door[9]:
  Path: door[9] -> coridor[22] -> coridor[21] -> coridor[20] -> exits[3]
  Distance: 42.12 ft
  Est. Time (Clear): 10.53 seconds
  Est. Time (Smoky): 28.08 seconds

From door[10]:
  Path: door[10] -> door[9] -> coridor[22] -> coridor[21] -> coridor[20] -> exits[3]
  Distance: 75.21 ft
  Est. Time (Clear): 18.80 seconds
  Est. Time (Smoky): 50.14 seconds
https://ideone.com/R9Qmcn
language:
C++ (gcc 8.3)
created:
3 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!