Leetcode — 980. Unique Paths III

The link to the problem: https://leetcode.com/problems/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
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)

Thoughts:

If you have solved 62. Unique Paths and 63. Unique Paths II on Leetcode, you might find that both of these questions can use dynamic programming to solve it. Since there are restrictions on our moving directions and we always start from top left to bottom right in problem 62 and 63, we can use a 2D array to store the number of paths so that the number of paths to the position (i, j) will always be the aggregation of the number of paths to its top cell and its left cell.

However, you will notice that this problem is totally different than the previous two problems. Now the starting and ending positions vary in every test case, we can forward all 4 directions in each cell, and we have to walk through each cell exactly one time. It is impossible for us to use dynamic programming to solve this problem since we need to keep track of the cells that we have walked through.

Since we will always have 4 directions to head to while we are on the current cell, these 4 cells are possible to be our next step. We will try to head to all these possible cells from the current position to see if we can create new possible paths based on the current choices. And yes, this is what backtracking does — we make a choice and keep making other choices based on the choice till we cannot continue the choices, then we redo the previous choices and make another choice.

Code Logic:

Before we start to make any choices (i.e., decide which cell we are going to step on next), we should first find the starting position and the total number of cells we should traverse.

Since we need to know which cells we have visited, I will use a List to record all the visited paths. If we found the current cell is invalid, has an obstacle, or has been visited, then we should redo the choice and choose another valid cell. We will continue traversing the next possible cells until we have traversed all the cells for the current path.

Below is the 20ms code that beats 5% —

public int uniquePathsIII(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[] start = new int[2];
        int count = 0;//number of 0s and starting point
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(grid[i][j]==1)
                {
                    start[0] = i;
                    start[1] = j;
                }
                else if(grid[i][j]==0)
                    count++;
            }
        }
        return helper(grid, start[0],start[1], count+1, new ArrayList<>());
    }
    public int helper(int[][] grid,int i,int j, int count, List<String> visited){
        if(i<0||j<0||i>=grid.length||j>=grid[i].length||grid[i][j]==-1 ||visited.contains(i+" "+j))
            return 0;
        if(grid[i][j]==2)
        {
            if(visited.size()==count)
                return 1;
            return 0;
        }
        visited.add(i+" "+j);
        int rst = 0;
        rst += helper(grid, i+1, j, count, new ArrayList<>(visited));
        rst += helper(grid, i-1, j, count, new ArrayList<>(visited));
        rst += helper(grid, i, j+1, count, new ArrayList<>(visited));
        rst += helper(grid, i, j-1, count, new ArrayList<>(visited));
        return rst;
    }

Since we are allowed to change the value of the given 2D array, we can also record the cells that we have visited in the 2D array.

After we visited the cells, we can put a stone (some obstacles) on the cell so that we won’t accidentally revisit them later. Hence, we will just set grid[i][j] to -1 and remove the stone (i.e., set grid[i][j] to 0) after we traversed all the possible paths based on the current cell.

Below is the 0ms code that beats 100% —

public int uniquePathsIII(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[] start = new int[2];
        int count = 0;//number of 0s and starting point
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(grid[i][j]==1)
                {
                    start[0] = i;
                    start[1] = j;
                }
                else if(grid[i][j]==0)
                    count++;
            }
        }
        return helper(grid, start[0],start[1], count+1);
    }
    public int helper(int[][] grid,int i,int j, int count){
        if(i<0||j<0||i>=grid.length||j>=grid[i].length||grid[i][j]==-1)
            return 0;
        if(grid[i][j]==2)
        {
            if(count==0)
                return 1;
            return 0;
        }
        grid[i][j] = -1;
        int rst = 0;
        rst += helper(grid, i+1, j, count-1);
        rst += helper(grid, i-1, j, count-1);
        rst += helper(grid, i, j+1, count-1);
        rst += helper(grid, i, j-1, count-1);
        grid[i][j] = 0;
        return rst;
    }