fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. bool maze[20][20]; //defined maze of maximum size 20x20
  6. bool visited[20][20];
  7.  
  8. bool Safe(int n, int m, int x, int y) //checking if a position is viable for moving through
  9. {
  10.     if(x >= 0 && x < n && y >= 0 && y < m)
  11.     {
  12.         if(maze[x][y] == 1) return true;
  13.     }
  14.     return false;
  15. }
  16.  
  17. bool Utility(int n, int m, int x, int y) //main utility function
  18. {
  19.     if(x == n - 1 && y == m - 1 && maze[x][y] == 1) // base case, end of maze
  20.     {
  21.         return true;
  22.     }
  23.  
  24.     if(!visited[x][y] && Safe(n, m, x, y))
  25.     {
  26.     	visited[x][y] = true;
  27.         if(Safe(n, m, x + 1, y)) // checking if it is viable to move down
  28.         {
  29.             if(Utility(n, m, x + 1, y))
  30.             {
  31.                 return true;
  32.             }
  33.         }
  34.         if(Safe(n, m, x, y + 1))
  35.         {
  36.             if(Utility(n, m, x, y + 1)) // checking if it is viable to move right
  37.             {
  38.                 return true;
  39.             }
  40.         }
  41.         if(Safe(n, m, x - 1, y))
  42.         {
  43.             if(Utility(n, m, x - 1, y)) // checking if it is viable to move up
  44.             {
  45.                 return true;
  46.             }
  47.         }
  48.         if(Safe(n, m, x, y - 1))
  49.         {
  50.             if(Utility(n, m, x, y - 1)) // checking if it is viable to move left
  51.             {
  52.                 return true;
  53.             }
  54.         }
  55.     }
  56.  
  57.     return false; // returning false
  58. }
  59.  
  60. int main()
  61. {
  62.     int n, m;
  63.  
  64.     cin >> n >> m; // input dimensions of the maze
  65.  
  66.     for(int i = 0; i < n; i++) // input maze
  67.     {
  68.         for(int j = 0; j < m; j++)
  69.         {
  70.             char c;
  71.             cin >> c;
  72.             if(c == '.') //character '.' means a tile which you can go through
  73.             {
  74.                 maze[i][j] = true;
  75.             }
  76.             else         //character 'x' means a tile which you cannot go through
  77.             {
  78.                 maze[i][j] = false;
  79.             }
  80.             visited[i][j] = false;
  81.         }
  82.     }
  83.  
  84.     if(Utility(n, m, 0, 0)) //printing yes or no
  85.     {
  86.         cout << "da";
  87.     }
  88.     else
  89.     {
  90.         cout << "ne";
  91.     }
  92.  
  93.  
  94.     return 0;
  95. }
Success #stdin #stdout 0s 4256KB
comments (?)
stdin 
8 8 
.x.....x 
.x.x.x.x 
.x.x.x.x 
.x.x.x.x 
.x.x.x.x 
.x.x.x.x 
.x.x.x.x 
...x.x..
stdout 
da
https://ideone.com/vVqAjF
language:
C++14 (gcc 8.3)
created:
3 years 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!