#include <bits/stdc++.h>
bool isValid(int x , int y , vector < vector<bool> > &visited , vector < vector <int> > &maze , int n) {
if(x < 0 || x >= n ) return false;
if(y < 0 || y >= n) return false;
if(visited[x][y] == 1) return false;
if(maze[x][y] == 0) return false;
return true;
}
// functiom to find all possible paths
void allPaths(int x , int y , vector < vector <int> > &maze , vector < vector <bool> > &visited , vector <vector<int> > &ans , int n) {
// base case
if(x == n -1 && y == n -1) {
visited[x][y] = 1;
int nrows = visited . size();
int ncols = visited[0] . size();
vector<int> temp;
for(int i = 0; i < nrows; i++) {
for(int j = 0; j < ncols; j++) {
temp . push_back(visited[i][j]);
}
}
ans . push_back(temp);
return ;
}
// up x - 1 , y
// down : x + 1 , y
// left :x , y - 1
// right : x , y + 1
// traversing all the paths and assume that recursion get the answer
// check whether particular cell is valid or not
// for up
if(isValid(x - 1 , y , visited , maze , n)) {
visited[x - 1][y] = 1;
allPaths( x - 1, y, maze, visited, ans ,n);
}
// for down
if(isValid(x + 1 , y , visited , maze , n)) {
visited[x + 1][y] = 1;
allPaths( x + 1, y, maze, visited, ans , n);
}
// for left
if(isValid(x , y - 1 , visited , maze , n)) {
visited[x][y - 1] = 1;
allPaths( x , y - 1, maze, visited, ans , n);
}
// for right
if(isValid(x , y + 1 , visited , maze , n)) {
visited[x][y + 1] = 1;
allPaths( x, y + 1, maze, visited, ans , n);
}
//backtracking steps
visited[x][y] = 0;
}
vector<vector<int> > ratInAMaze(vector<vector<int> > &maze, int n){
// visited array which keeps track of the visited position
vector< vector<bool> > visited(n , vector<bool>(n , false));
// ans array which stores all the paths
vector < vector<int> > ans;
allPaths(0, 0, maze, visited, ans , n);
return ans;
}