Posted on by tzry

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

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;
   
}


14 Replies to “LeetCode 980. Unique Paths III”

  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

    Reply

  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

    Reply

  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

    Reply

  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

    Reply

  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

    Reply

  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

    Reply

  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

    Reply

  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

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *