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.
1class Solution {
2 private int paths = 0, empty = 1;
3 public int uniquePathsIII(int[][] grid) {
4 int start_x = 0, start_y = 0;
5
6 for (int i = 0; i < grid.length; i++) {
7 for (int j = 0; j < grid[0].length; j++) {
8 if (grid[i][j] == 0) empty++;
9 else if (grid[i][j] == 1) { start_x = i; start_y = j; }
10 }
11 }
12
13 dfs(grid, start_x, start_y, empty);
14 return paths;
15 }
16
17 private void dfs(int[][] grid, int x, int y, int remain) {
18 if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length || grid[x][y] < 0) return;
19 if (grid[x][y] == 2) { if (remain == 0) paths++; return; }
20 grid[x][y] = -2;
21 dfs(grid, x + 1, y, remain - 1);
22 dfs(grid, x - 1, y, remain - 1);
23 dfs(grid, x, y + 1, remain - 1);
24 dfs(grid, x, y - 1, remain - 1);
25 grid[x][y] = 0;
26 }
27}The Java solution, similarly, uses DFS traversing each possible path via recursion and backtracking. The approach extracts coordinates for the starting position and counts empty spaces. The implementation handles recursion within a helper function, altering the grid to signify visited states and reversing those states during backtracking.
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.