980. Unique Paths III

Problem

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.

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)

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)

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. 1 <= grid.length * grid[0].length <= 20

Discussion

This problem requires us to find all unique paths from point 1 to 2.

As this requires iterations through all elements and all paths between two points, we may come up with the idea of using DFS. Things become straight forward now as actually this problem is very similar to 79. Word Search, which is obvious a DFS and back-tracking problem.

Besides DFS and back-tracking to find all unique paths, we also have to make sure all 0 is being used exactly once in the paths, and no other values besides 0 and 1 are used. Achieving this we simply count all the 0 in grid and do validation.

Solution

We begin our solution with a loop finding all the 0 in the grid, and scanning 1 to begin our DFS method. We use DFS by recursion here for simplicity.

In the DFS, we temporary update the visited node to some special value (999) to prevent re-use of the same element in the grid and we restore the value after each iteration.

Besides we maintain a variable step to see how many 0 or 1 is visited. When we reach 2, we check the value of step to see if all 0 are being passed through exactly once. Then we update our result number if a new unique path is founded.

from typing import List

class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        self.grid = grid
        self.result = 0
        self.number_of_zero = 0

        for i in range(len(grid)):
            for j in range(len(grid[i])):
                if grid[i][j] == 0:
                    self.number_of_zero += 1

        for i in range(len(grid)):
            for j in range(len(grid[i])):
                if grid[i][j] == 1:
                    self.dfs(i, j, 0)
        return self.result


    def dfs(self, i, j, step):
        if self.grid[i][j] == 2:
            if step == self.number_of_zero + 1:
                self.result += 1
            return


        if self.grid[i][j] in (0, 1):
            temp, self.grid[i][j] = self.grid[i][j], 999

            if i > 0:
                self.dfs(i - 1, j, step + 1)

            if j > 0:
                self.dfs(i, j - 1, step + 1)

            if i < len(self.grid) - 1:
                self.dfs(i + 1, j, step + 1)

            if j < len(self.grid[0]) - 1:
                self.dfs(i, j + 1, step + 1)

            self.grid[i][j] = temp

        return

Complexity Analysis

• Time Complexity: O(3^n), as although we have 4 directions go search in each iteration, we have at most 3 directions to go in each iteration.
• Space Complexity: O(n), as we apply recursion which at most holding n layer of instances. Besides only the input grid and other constant variables are maintained in memory.