On a 2-dimensional grid, there are 4 types of squares:
1 represents the starting square. There is exactly one starting square.
2 represents the ending square. There is exactly one ending square.
0 represents empty squares we can walk over.
-1 represents obstacles that we cannot walk over.
Return the number of 4-directional walks from the starting square to the ending square, that walk over every non-obstacle square exactly once.
Example 1:
Input: [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output: 2
Explanation: We have the following two paths:
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)
Example 2:
Input: [[1,0,0,0],[0,0,0,0],[0,0,0,2]]
Output: 4
Explanation: We have the following four paths:
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
2. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
3. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
4. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)
Example 3:
Input: [[0,1],[2,0]]
Output: 0
Explanation:
There is no path that walks over every empty square exactly once.
Note that the starting and ending square can be anywhere in the grid.
Note:
1 <= grid.length * grid[0].length <= 20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | void uniquePathsIIILogic(int** grid, int gridSize, int gridColSize, int nowRow, int nowCol, int* cnt, int depthLeft){ if(depthLeft<0 || nowRow<0||nowRow>=gridSize||nowCol<0||nowCol>=gridColSize){ return; } if(depthLeft==0){ if(grid[nowRow][nowCol]==2){ ++*cnt; } } else if(grid[nowRow][nowCol]==2){ return; } else if(grid[nowRow][nowCol]>=0){ grid[nowRow][nowCol]-=3; uniquePathsIIILogic( grid,gridSize,gridColSize,nowRow-1,nowCol,cnt,depthLeft-1 ); uniquePathsIIILogic( grid,gridSize,gridColSize,nowRow+1,nowCol,cnt,depthLeft-1 ); uniquePathsIIILogic( grid,gridSize,gridColSize,nowRow,nowCol-1,cnt,depthLeft-1 ); uniquePathsIIILogic( grid,gridSize,gridColSize,nowRow,nowCol+1,cnt,depthLeft-1 ); grid[nowRow][nowCol]+=3; } } int uniquePathsIII(int** grid, int gridSize, int* gridColSize){ int startRow, startCol, depth=1; for(int i=0;i<gridSize;++i){ for(int j=0;j<*gridColSize;++j){ if(grid[i][j]==1){ startRow=i; startCol=j; } else if(grid[i][j]==0){ ++depth; } } } int cnt = 0; uniquePathsIIILogic(grid,gridSize,*gridColSize,startRow,startCol,&cnt,depth); return cnt; } |