LeetCode 980. Unique Paths III

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

 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152 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

14 Replies to “LeetCode 980. Unique Paths III”

1. Thankyou for this practical advice on what is normally a forgotten topic. Is it okay to link this with my people? Neysa Jay Finnigan

2. Do you mind if I quote a couple of your posts as long as I provide credit and sources back to your site? My website is in the exact same area of interest as yours and my users would definitely benefit from a lot of the information you present here. Please let me know if this alright with you. Thanks! Corissa Cornie Vitalis

3. Programming is still in its infancy. In fact, two of the very first programming languages ever invented are still being used today Berte Sergio Mozart

4. I’m usually to blogging and i really admire your content. The article has really peaks my interest. I am going to bookmark your website and maintain checking for brand spanking new information. Brynna Kermie Garfield

5. I am not sure where you are getting your info, but great topic. I needs to spend some time learning more or understanding more. Thanks for wonderful info I was looking for this information for my mission. Alfie Durant Ames

6. Nice blog right here! Also your website so much up very fast! What host are you the use of? Can I am getting your associate link to your host? I want my site loaded up as fast as yours lol Agata Braden Docilu

7. There is definately a lot to learn about this issue. I like all of the points you ave made. Susanna Cosimo Boyden

8. Somebody necessarily help to make significantly posts I would state. That is the first time I frequented your web page and to this point? I amazed with the analysis you made to make this actual submit incredible. Wonderful activity! Jess Ari Dare

9. Hey there! I simply wish to give you a big thumbs up for the excellent information you have here on this post. I am returning to your web site for more soon.| Midge Michal Selwyn

10. great post, i undoubtedly love this site, keep on it Michel Ingmar Gokey

11. Very interesting points you have remarked, appreciate it for putting up. Rozalin Nils Dunham

12. Wow, awesome weblog layout! How lengthy have you ever been running a blog for? you made blogging look easy. The full glance of your website is wonderful, let alone the content! Midge Consalve Neilla

13. Hi there. I discovered your website by way of Google at the same time as searching for a similar topic, your website came up. It looks great. I have bookmarked it in my google bookmarks to come back then. Cornie Arnuad Atalya