LeetCode 980. Unique Paths III

September 14, 2020

We could think of the $grid$ as a graph where $\{0, 1, 2\}$ are nodes, any shared edge in the grid is a graph edge, and $-1$ is ignored.

This could be described as a graph search that ignores cycles. But it's more complicated because a path has to touch every node.

Naively, we could do a graph search from the start node to the end node, and then return the count of paths that are the correct length.

I think that's actually the best we can do. This solution would be $O(n!)$ for a complete graph, but our graph is limited to 3 edges per node (only the first node has 4 edges). This solution is $O(3^n)$ .

Using a DFS is probably easiest since it implicitly provides us with the path we've taken to get to the end node.

from typing import List
import unittest

class Test(unittest.TestCase):

    def setUp(self):
        self.s = Solution()

    def test_examples(self):
        self.assertEqual(self.s.uniquePathsIII([[1,0,0,0],[0,0,0,0],[0,0,2,-1]]), 2)
        self.assertEqual(self.s.uniquePathsIII([[1,0,0,0],[0,0,0,0],[0,0,0,2]]), 4)
        self.assertEqual(self.s.uniquePathsIII([[0,1],[2,0]]), 0)

    def test_obstacles(self):
        self.assertEqual(self.s.uniquePathsIII([[1,0,0],[-1,-1,-1],[2,0,0]]), 0)
        self.assertEqual(self.s.uniquePathsIII([[1,0,0],[-1,-1,0],[2,0,0]]), 1)

class Solution:

    def _dfs_helper(self, grid: List[List[int]], ni: int, nj: int, seen: set) -> List[int]:
        """Does a DFS and returns a List of path lengths from start to end node.

        Args:
            grid: A graph represented as a 2d List.
            ni: The row index of the current node.
            nj: The column index of the current node.
            seen: A set of nodes already crossed on this path.

        Returns:
            List[int]: A List of path lengths from start to end node.
        """
        if (ni,nj) in seen:
            return []
        seen.add((ni,nj))
        if ni < 0 or ni >= len(grid) or nj < 0 or nj >= len(grid[ni]):
            return []
        if grid[ni][nj] == -1:
            seen.remove((ni,nj))
            return []
        if grid[ni][nj] == 2:
            seen.remove((ni,nj))
            return [1]
        counts = []
        for i in (ni-1, ni+1):
            counts.extend(self._dfs_helper(grid, i, nj, seen))
        for j in (nj-1, nj+1):
            counts.extend(self._dfs_helper(grid, ni, j, seen))
        seen.remove((ni,nj))
        return [c+1 for c in counts]

    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        parent = {}
        ri = rj = 0
        n = 0
        for i in range(len(grid)):
            for j in range(len(grid[i])):
                if grid[i][j] == -1:
                    continue
                n += 1
                if grid[i][j] == 1:
                    ri, rj = i, j
        counts = self._dfs_helper(grid, ri, rj, set())
        return sum([1 if n == c else 0 for c in counts])

if __name__ == "__main__":
    unittest.main()