Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- using namespace std;
- int a[1010][1010];
- int count = 0;
- char ch[1010][1010];
- bool ratInMaze(int i, int j, int m, int n){
- // cout<<m<<" "<<n<<endl;
- if(count == 1)
- return true;
- if(i > m || j > n )
- return false;
- if(i == m && j == n){
- a[m][n] = 1;
- for(int i = 1; i <= m; i++){
- for(int j = 1; j <= n; j++)
- cout<<a[i][j]<<" ";
- cout<<endl;
- }
- count = 1;cout<<endl;cout<<endl;cout<<endl;
- return true;
- }
- if(ch[i][j] == 'X')
- return false;
- a[i][j] = 1;
- bool rightSuccess = ratInMaze(i, j+1, m, n);
- bool leftSuccess = ratInMaze(i+1, j, m, n);
- if(rightSuccess || leftSuccess)
- return true;
- //backtrack
- a[i][j] = 0;
- return false;
- }
- int main(){
- int n, m;
- cin>>m>>n;
- for(int i = 1; i <= m; i++)
- for(int j = 1; j <= n; j++)
- cin>>ch[i][j];
- bool p = ratInMaze(1, 1, m, n);
- if(!p)
- cout<<-1<<endl;
- }
Add Comment
Please, Sign In to add comment