< Back




980. Unique Paths III

Fun problem, I LOVE GRAPHS. We're given a grid, size m * n, where each cell has a number that
represents something. Our start point is grid[i][j] == 1, and our end point is grid[i][j] == 2. We
have empty cells that we can walk over where grid[i][j] == 0, and obstacles where grid[i][j] == -1.

We're asked to find all paths to the end that touch all empty grid locations exactly once. This is
easily recognizable as a backtracking problem with DFS, however, we can't use the iterative version
of DFS because we need to maintain a separate context for the seen set as we visit each path.

We start off by gathering information, finding the start and end points, as well as counting the
number of empty cells. We the start our backtracking from the start point, already having it marked
as seen so we don't revisit it. At each node in the graph, we check our neighbors to see if they're
valid. If so, we attempt to visit them.

Before visiting a neighbor, we check to see if it's the end. If it is, we check to see if we visited
all the empty cells we counted. If we haven't yet, we skip visiting the end. Otherwise, we visit the
end and increment our answer.

The solution is as follows:


  class Solution:
      def uniquePathsIII(self, grid: List[List[int]]) -> int:
          directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
          m, n = len(grid), len(grid[0])
          start, end = (0, 0), (m - 1, n - 1)
          empties = self.ans = 0

          for i in range(m):
              for j in range(n):
                  if grid[i][j] == 0:
                      empties += 1
                  elif grid[i][j] == 1:
                      start = (i, j)
                  elif grid[i][j] == 2:
                      end = (i, j)

          def valid(i: int, j: int) -> bool:
              return -1 < i < m and -1 < j < n and grid[i][j] != -1

          def backtrack(node: tuple, seen: set, c: int) -> None:
              y, x = node

              if (y, x) == end:
                  self.ans += 1
                  return

              for dy, dx in directions:
                  ny, nx = y + dy, x + dx

                  if valid(ny, nx) and (ny, nx) not in seen:
                      if (ny, nx) == end and c != empties:
                          continue

                      seen.add((ny, nx))
                      backtrack((ny, nx), seen, c + 1)
                      seen.remove((ny, nx))

          backtrack(start, {start}, 0)

          return self.ans


_ Time Complexity:

  O(3^n) - Where n is the number of empty cells, we make at most 3 recursive calls at each node.

_ Space Complexity:

  O((m * n) + n) - We store at most m * n nodes in our seen set, and n is the number of empty cells.