fork download
copy 
  1. //
  2. //  main.cpp
  3. //  Rat in the Maze
  4. //
  5. //  Created by Himanshu on 25/09/21.
  6. //
  7.  
  8. #include <iostream>
  9. using namespace std;
  10. const int N = 4;
  11.  
  12. void printPath(int sol[][N]) {
  13.     for (int i=0; i<N; i++) {
  14.         for (int j=0; j<N; j++) {
  15.             cout<<sol[i][j]<<" ";
  16.         }
  17.         cout<<endl;
  18.     }
  19. }
  20.  
  21. bool solve (int maze[N][N], int x, int y, int sol[N][N]) {
  22.     if (x == N-1 && y == N-1) {
  23.         sol[x][y] = 1;
  24.         return true;
  25.     }
  26.  
  27.     if (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1) {
  28.         sol[x][y] = 1;
  29.  
  30.         if (solve(maze, x+1, y, sol)) {
  31.             return true;
  32.         }
  33.         if (solve(maze, x, y+1, sol)) {
  34.             return true;
  35.         }
  36.  
  37.         sol[x][y] = 0;
  38.     }
  39.  
  40.     return false;
  41. }
  42.  
  43. int main() {
  44.     int maze[N][N] = {{1, 1, 0, 0},
  45.                      {1, 1, 1, 0},
  46.                      {0, 1, 0, 1},
  47.                      {0, 1, 1, 1}};
  48.  
  49.     int sol[N][N];
  50.     for (int i=0; i<N; i++) {
  51.         for (int j=0; j<N; j++) {
  52.             sol[i][j] = 0;
  53.         }
  54.     }
  55.  
  56.     if (solve(maze, 0, 0, sol)) {
  57.         cout<<"Path exists. Path is marked with 1:"<<endl;
  58.         printPath(sol);
  59.     } else {
  60.         cout<<"Path does not exist";
  61.     }
  62.  
  63.     return 0;
  64. }
Success #stdin #stdout 0.01s 5408KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Path exists. Path is marked with 1:
1 0 0 0 
1 1 0 0 
0 1 0 0 
0 1 1 1
https://ideone.com/JhwF2t
language:
C++ 4.3.2 (gcc-4.3.2)
created:
1 year ago
visibility:
secret

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!