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.
1#include <stdio.h>
2int uniquePathsIII(int** grid, int gridSize, int* gridColSize) {
3 int rows = gridSize, cols = gridColSize[0], start_r, start_c, empty = 1, paths = 0;
4
5 for (int r = 0; r < rows; ++r) {
6 for (int c = 0; c < cols; ++c) {
7 if (grid[r][c] == 0) empty++;
8 else if (grid[r][c] == 1) { start_r = r; start_c = c; }
9 }
10 }
11
12 void dfs(int r, int c, int remain) {
13 if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] < 0) return;
14 if (grid[r][c] == 2) { if (remain == 0) paths++; return; }
15 grid[r][c] = -2;
16 dfs(r+1, c, remain-1);
17 dfs(r-1, c, remain-1);
18 dfs(r, c+1, remain-1);
19 dfs(r, c-1, remain-1);
20 grid[r][c] = 0;
21 }
22
23 dfs(start_r, start_c, empty);
24 return paths;
25}This C implementation follows similar logic. We initialize essential variables and create a nested function dfs() to handle recursion. The grid is traversed to determine starting point coordinates and count empty squares. Using DFS recursion, the function explores all potential paths, verifies conditions, and returns the total count of valid paths via backtracking method.
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.