Unique Paths III
Tags: leetcode, dsa, theabbie
Published: 2022-06-15 09:00:47

You are given an `m x n` integer array `grid` where `grid[i][j]` could be:

*   `1` representing the starting square. There is exactly one starting square.
*   `2` representing the ending square. There is exactly one ending square.
*   `0` representing empty squares we can walk over.
*   `-1` representing 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:**

![](https://assets.leetcode.com/uploads/2021/08/02/lc-unique1.jpg)

**Input:** grid = \[\[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:**

![](https://assets.leetcode.com/uploads/2021/08/02/lc-unique2.jpg)

**Input:** grid = \[\[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:**

![](https://assets.leetcode.com/uploads/2021/08/02/lc-unique3-.jpg)

**Input:** grid = \[\[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.

**Constraints:**

*   `m == grid.length`
*   `n == grid[i].length`
*   `1 <= m, n <= 20`
*   `1 <= m * n <= 20`
*   `-1 <= grid[i][j] <= 2`
*   There is exactly one starting cell and one ending cell.

**SOLUTION:**

    class Solution:
        def getNeighbors(self, start, m, n):
            a, b = start
            neighbors = []
            if a > 0:
                neighbors.append((a - 1, b))
            if a < m - 1:
                neighbors.append((a + 1, b))
            if b > 0:
                neighbors.append((a, b - 1))
            if b < n - 1:
                neighbors.append((a, b + 1))
            return neighbors
        
        def unipaths(self, start, grid, visited, m, n, numEmpty):
            currval = grid[start[0]][start[1]]
            ways = 0
            if currval == -1:
                return ways
            if currval == 2:
                if len(visited) == numEmpty + 2:
                    return ways + 1
                return ways
            neighbors = self.getNeighbors(start, m, n)
            for neighbor in neighbors:
                if grid[neighbor[0]][neighbor[1]] != -1 and neighbor not in visited:
                    ways += self.unipaths(neighbor, grid, visited.union({neighbor}), m, n, numEmpty)
            return ways
        
        def uniquePathsIII(self, grid: List[List[int]]) -> int:
            m = len(grid)
            n = len(grid[0])
            numEmpty = 0
            start = None
            for i in range(m):
                for j in range(n):
                    if grid[i][j] == 0:
                        numEmpty += 1
                    elif grid[i][j] == 1:
                        start = (i, j)
            return self.unipaths(start, grid, {start}, m, n, numEmpty)