| 1 | /*Brute Forced DFS solution*/ |
| 2 | |
| 3 | class Solution { |
| 4 | public: |
| 5 | int paths = 0; |
| 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 | { |
| 40 | int startPosX = 0; |
| 41 | int startPosY = 0; |
| 42 | int id = 1; |
| 43 | //Find the starting position |
| 44 | for (int i = 0; i < grid.size(); i++) |
| 45 | { |
| 46 | for (int j = 0; j < grid[0].size(); j++) |
| 47 | { |
| 48 | if (grid[i][j] == 1) |
| 49 | { |
| 50 | //Get the postion of starting square |
| 51 | startPosX = i; |
| 52 | startPosY = j; |
| 53 | } |
| 54 | else if(grid[i][j] == 0) |
| 55 | { |
| 56 | obstacles++; |
| 57 | } |
| 58 | } |
| 59 | } |
| 60 | //Initialize the visited matrix |
nothing calls this directly
no outgoing calls
no test coverage detected