Unique Paths III Problem

Question

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 1:

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)

Example 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)

Example 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

Answer 1

Intuition

We can consider backtracking as a state machine, where we start off from an initial state, each action we take will move the state from one to another, and there should be some final state where we reach our goal.

As a result, let us first clarify the initial and the final states of the problem.

• Initial State

  • There are different types of squares/cells in a grid.

  • There are an origin and a destination cell, which are not given explicitly.

  • Initially, all the cells are not visited.

• Final State

  • We reach the destination cell, i.e. cell filled with the value 2.

  • We have visited all the non-obstacle cells, including the empty cells (i.e. filled with 0) and the initial cell (i.e. 1).

With the above definition, we can then translate the problem as finding all paths that can lead us from the initial state to the final state.

More specifically, we could summarise the steps to implement the backtracking algorithm for this problem in the following pseudo code.

    def backtrack(cell):
        1. if we arrive at the final state:
             path_count ++
             return

        2. mark the current cell as visited

        3. for next_cell in 4 directions:
             if next_cell is not visited and non-obstacle:
                 backtrack(next_cell)

        4. unmark the current cell

Algorithm

As one can see, backtracking is more of a methodology to solve a specific type of problems. For a backtracking problem, it would not be exaggerating to say that there are a thousand backtracking implementations in a thousand people's eyes, as one would find out in the implementation later.

class Solution:     def uniquePathsIII(self, grid: List[List[int]]) -> int:         rows, cols = len(grid), len(grid[0])         # step 1). initialize the conditions for backtracking         #   i.e. initial state and final state         non_obstacles = 0         start_row, start_col = 0, 0         for row in range(0, rows):             for col in range(0, cols):                 cell = grid[row][col]                  if  cell >= 0:                     non_obstacles += 1                 if cell == 1:                     start_row, start_col = row, col         # count of paths as the final result         path_count = 0         # step 2). backtrack on the grid         def backtrack(row, col, remain):             # we need to modify this external variable             nonlocal path_count             # base case for the termination of backtracking             if grid[row][col] == 2 and remain == 1:                 # reach the destination                 path_count += 1                 return             # mark the square as visited. case: 0, 1, 2              temp = grid[row][col]              grid[row][col] = -4             remain -= 1   # we now have one less square to visit             # explore the 4 potential directions around             for ro, co in [(0, 1), (0, -1), (1, 0), (-1, 0)]:                 next_row, next_col = row + ro, col + co                 if not (0 <= next_row < rows and 0 <= next_col < cols):                     # invalid coordinate                     continue                 if grid[next_row][next_col] < 0:                     # either obstacle or visited square                     continue                 backtrack(next_row, next_col, remain)             # unmark the square after the visit             grid[row][col] = temp         backtrack(start_row, start_col, non_obstacles)         return path_count

eg : grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]

ans = Solution()

ans.uniquePathsIII(grid)

Output -

2