Sponsored
Sponsored
This approach uses a Depth-First Search (DFS) technique with backtracking to explore every possible path from the start to the end square. We first count all the empty squares and ensure that each path covers all these squares exactly once. Starting from the initial position, we recursively visit adjacent squares, marking them as visited to ensure they aren't visited again during the same path. If a path reaches the end square and has visited all empty squares, it's a valid path.
Time Complexity: O(3^(m*n)). In the worst case, we explore each cell in multiple directions.
Space Complexity: O(m*n), due to recursion stack.
1def uniquePathsIII(grid):
2 def dfs(x, y, remain):
3 if not (0 <= x < rows and 0 <= y < cols and grid[x][y] >= 0):
4 return 0
5 if grid[x][y] == 2:
6 return remain == 1
7 grid[x][y] = -2 # mark as visited
8 paths = dfs(x + 1, y, remain - 1) + dfs(x - 1, y, remain - 1) + \
9 dfs(x, y + 1, remain - 1) + dfs(x, y - 1, remain - 1)
10 grid[x][y] = 0 # un-mark as visited
11 return paths
12
13 rows, cols = len(grid), len(grid[0])
14 start = sum(x.count(1) for x in grid) # locate the start point
15 empty = sum(x.count(0) for x in grid) + 1 # count empty cells including start point
16
17 for r in range(rows):
18 for c in range(cols):
19 if grid[r][c] == 1:
20 start_r, start_c = r, c
21 break
22
23 return dfs(start_r, start_c, empty)The solution uses DFS to explore all possible paths recursively. The dfs() function is defined to attempt moving in four directions from the current cell. We mark the current cell as visited by temporarily setting it to -2 and backtrack by restoring its value to 0, enabling alternative paths. We use a counter variable, remain, to track the number of unvisited non-obstacle squares. If we reach the target square after visiting all non-obstacle squares, it's counted as one unique path.
In this approach, we use dynamic programming to reduce the problem into smaller overlapping subproblems. With state compression, we leverage bitmasking to track visited squares in the grid efficiently. Each state is represented by a combination of the current cell and a bitmask that indicates which of the necessary cells (squares) have been covered. The problem then simplifies into finding paths to cover large subproblems using previously computed smaller subproblem solutions.
Time Complexity: O(m * n * 2^{mn}), based on distinct achievable states across board size.
Space Complexity: O(m * n * 2^{mn}), attributed to DP table size.
1def uniquePathsIII(grid):
2 m, n = len(grid
This method involves initializing a 2D DP table and iteratively computing the number of paths by considering smaller subsets of the grid using bitmask representation. Each cell represents the state of paths leading to it, which can be updated from adjacent cells. This method maximizes efficiency by avoiding repetitive computations, combining overlapping solutions with dynamic programming. Details are omitted due to space limitations.