| 6 | int obstacles = 0; |
| 7 | |
| 8 | void dfs(vector<vector<int>>& grid, int x,int y,int walked, vector<vector<bool>> visited) |
| 9 | { |
| 10 | //Check if the position is out of boundries or the position is already visited |
| 11 | if (x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size() || grid[x][y] == -1 || visited[x][y]) |
| 12 | { |
| 13 | return; |
| 14 | } |
| 15 | |
| 16 | //If we arrivied at the ending square so increase the number of paths by one |
| 17 | if (grid[x][y] == 2) |
| 18 | { |
| 19 | if (obstacles == walked - 1) |
| 20 | { |
| 21 | paths++; |
| 22 | } |
| 23 | return; |
| 24 | } |
| 25 | |
| 26 | visited[x][y] = true; |
| 27 | //Check Right Square |
| 28 | dfs(grid,x+1,y,walked+1,visited); |
| 29 | //Check Left Square |
| 30 | dfs(grid,x-1,y,walked+1,visited); |
| 31 | //Check Top Square |
| 32 | dfs(grid,x,y+1,walked+1,visited); |
| 33 | //Check Bottom Square |
| 34 | dfs(grid,x,y-1,walked+1,visited); |
| 35 | visited[x][y] = false; |
| 36 | } |
| 37 | |
| 38 | int uniquePathsIII(vector<vector<int>>& grid) |
| 39 | { |