C++/ BFS
Assuming a path exits, we can do a simple dfs from top left to bottom right.
- The BFS call will also store two counters right, down which we will increment every time we move in that direction.
- If
right < 2 && down < 2
we have can move in both the directions (right and down). When you move right, set down to 0 and vice-versa.
- If
right < 2
more right and set down counter to 0.
- If
down < 2
more down and set right counter to 0.
#define pp pair<int, int>
void bfs(vector< vector<int> > &grid, int x, int y, int right, int down, int &ct, queue<pp> q){
if(x == grid.size()-1 && y == grid[0].size()-1){
ct += 1;
q.push({x,y});
while(!q.empty()){
if(q.size() == 1)
cout << "(" <<q.front().first << " " << q.front().second << ") -> " << ct <<"\n";
else
cout << "(" <<q.front().first << " " << q.front().second << "), ";
q.pop();
}
return;
}
q.push({x,y});
if(right <2 && down <2){
if(y+1 < grid[0].size() && grid[x][y+1] == 1) dfs(grid, x, y+1, right+1, 0, ct, q);
if(x+1 < grid.size() && grid[x+1][y] == 1) dfs(grid, x+1, y, 0, down+1, ct, q);
} else if(right < 2){
if(y+1 < grid[0].size() && grid[x][y+1] == 1) dfs(grid, x, y+1, right+1, 0, ct, q);
} else{
if(x+1 < grid.size() && grid[x+1][y] == 1) dfs(grid, x+1, y, 0, down+1, ct, q);
}
return;
}
int main() {
vector<vector<int>> grid{{1,1,1},{1,1,1},{1,1,1}};
queue<pp> q;
int ct = 0;
bfs(grid, 0, 0, 0, 0, ct, q);
}
Output
(0 0), (0 1), (0 2), (1 2), (2 2) -> 1
(0 0), (0 1), (1 1), (1 2), (2 2) -> 2
(0 0), (0 1), (1 1), (2 1), (2 2) -> 3
(0 0), (1 0), (1 1), (1 2), (2 2) -> 4
(0 0), (1 0), (1 1), (2 1), (2 2) -> 5
(0 0), (1 0), (2 0), (2 1), (2 2) -> 6