Guest User

Untitled

a guest
Jan 2nd, 2020
116
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.09 KB | None | 0 0
  1. #include<iostream>
  2. using namespace std;
  3.  
  4. int a[1010][1010];
  5. int count = 0;
  6. char ch[1010][1010];
  7. bool ratInMaze(int i, int j, int m, int n){
  8.      // cout<<m<<"  "<<n<<endl;
  9.      if(count == 1)
  10.         return true;
  11.     if(i > m || j > n )
  12.         return false;
  13.     if(i == m && j == n){
  14.          a[m][n] = 1;
  15.          for(int i = 1; i <= m; i++){
  16.               for(int j = 1; j <= n; j++)
  17.                 cout<<a[i][j]<<" ";
  18.               cout<<endl;
  19.              
  20.          }
  21.          count = 1;cout<<endl;cout<<endl;cout<<endl;
  22.            return true;
  23.        
  24.     }
  25.     if(ch[i][j] == 'X')
  26.         return false;
  27.    
  28.     a[i][j] = 1;
  29.    bool rightSuccess = ratInMaze(i, j+1, m, n);
  30.    bool leftSuccess = ratInMaze(i+1, j, m, n);
  31.     if(rightSuccess || leftSuccess)
  32.         return true;
  33.     //backtrack
  34.     a[i][j] = 0;
  35.     return false;
  36. }
  37.  
  38. int main(){
  39.     int n, m;
  40.     cin>>m>>n;
  41.    
  42.     for(int i = 1; i <= m; i++)
  43.         for(int j = 1; j <= n; j++)
  44.             cin>>ch[i][j];
  45.    
  46.        
  47.     bool p = ratInMaze(1, 1, m, n);
  48.     if(!p)
  49.         cout<<-1<<endl;
  50. }
Add Comment
Please, Sign In to add comment