fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <algorithm>
  5. #include <ctime>
  6. #include <climits>
  7. #include <cstring>
  8. using namespace std;
  9.  
  10. const int N = 21;
  11. char maze[N][N];
  12. bool visited[N][N];
  13. int dx[] = {0, 0, -2, 2};
  14. int dy[] = {-2, 2, 0, 0};
  15.  
  16. void generateMaze(int x, int y) {
  17.     visited[x][y] = true;
  18.     maze[x][y] = ' ';
  19.     vector<int> dirs = {0, 1, 2, 3};
  20.     random_shuffle(dirs.begin(), dirs.end());
  21.  
  22.     for (int i : dirs) {
  23.         int nx = x + dx[i], ny = y + dy[i];
  24.         if (nx > 0 && ny > 0 && nx < N - 1 && ny < N - 1 && !visited[nx][ny]) {
  25.             maze[x + dx[i] / 2][y + dy[i] / 2] = ' ';
  26.             generateMaze(nx, ny);
  27.         }
  28.     }
  29. }
  30.  
  31. struct Node {
  32.     int x, y, dist;
  33.     bool operator>(const Node& other) const {
  34.         return dist > other.dist;
  35.     }
  36. };
  37.  
  38. int dijkstra(pair<int, int> start, pair<int, int> end, vector<vector<int>>& dist) {
  39.     priority_queue<Node, vector<Node>, greater<Node>> pq;
  40.     pq.push({start.first, start.second, 0});
  41.     dist[start.first][start.second] = 0;
  42.  
  43.     while (!pq.empty()) {
  44.         Node cur = pq.top(); pq.pop();
  45.         if (cur.x == end.first && cur.y == end.second)
  46.             return cur.dist;
  47.  
  48.         for (int i = 0; i < 4; i++) {
  49.             int nx = cur.x + dx[i] / 2, ny = cur.y + dy[i] / 2;
  50.             if (nx >= 0 && ny >= 0 && nx < N && ny < N && maze[nx][ny] == ' ') {
  51.                 int new_dist = cur.dist + 1;
  52.                 if (new_dist < dist[nx][ny]) {
  53.                     dist[nx][ny] = new_dist;
  54.                     pq.push({nx, ny, new_dist});
  55.                 }
  56.             }
  57.         }
  58.     }
  59.     return -1;
  60. }
  61.  
  62. void printMaze(const vector<vector<int>>& dist, pair<int, int> end) {
  63.     for (int i = 0; i < N; ++i) {
  64.         for (int j = 0; j < N; ++j) {
  65.             if (i == end.first && j == end.second)
  66.                 cout << 'E';
  67.             else if (dist[i][j] != INT_MAX)
  68.                 cout << '.';
  69.             else
  70.                 cout << maze[i][j];
  71.         }
  72.         cout << endl;
  73.     }
  74. }
  75.  
  76. int main() {
  77.     srand(time(0));
  78.     memset(maze, '#', sizeof maze);
  79.     memset(visited, 0, sizeof visited);
  80.  
  81.     generateMaze(1, 1);
  82.  
  83.     pair<int, int> start = {1, 1};
  84.     pair<int, int> end = {N - 2, N - 2};
  85.  
  86.     vector<vector<int>> dist(N, vector<int>(N, INT_MAX));
  87.     int pathLength = dijkstra(start, end, dist);
  88.  
  89.     cout << "Generated Maze with shortest path marked:\n";
  90.     printMaze(dist, end);
  91.     cout << "\nShortest path length: " << pathLength << endl;
  92.  
  93.     return 0;
  94. }
Success #stdin #stdout 0s 5300KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Generated Maze with shortest path marked:
#####################
#.....#.....#       #
#####.###.#.####### #
#   #...#.#.......# #
# # ###.#.#######.# #
# #   #.#...#.#...# #
# ### #.#.#.#.#.### #
# # # #.#.#.#.#.#   #
#.# # #.###.#.#.### #
#.# # #.....#...#   #
#.# # #######.### # #
#.# #   #...#...# # #
#.# ### #.#.###.# ###
#.#   # #.#.....#   #
#.### # #.####### #.#
#...#   #.#   #   #.#
###.#####.# ### ###.#
#...#.....#     #...#
#.###.###########.#.#
#.................#E#
#####################

Shortest path length: 92
https://ideone.com/ZUPis9
language:
C++ (gcc 8.3)
created:
14 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!