Skip to main content

Unique Paths III

Problem Statement​

Problem Description​

You are given an m x n integer array grid where grid[i][j] could be:

  • 1 representing the starting square. There is exactly one starting square.
  • 2 representing the ending square. There is exactly one ending square.
  • 0 representing empty squares we can walk over.
  • -1 representing 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​

Example 1:

Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output: 2

Explanation: We have the following two paths:

(0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(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: grid = [[1,0,0,0],[0,0,0,0],[0,0,0,2]]
Output: 4

Explanation: We have the following four paths:

(0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3) (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,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) (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)

Constraints​

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 20
  • 1 <= m * n <= 20
  • -1 <= grid[i][j] <= 2
  • There is exactly one starting cell and one ending cell.

Solution​

Intuition​

To solve this problem, we can use a backtracking approach with Depth-First Search (DFS). We will start from the starting square and try to explore all possible paths to the ending square while ensuring we visit every non-obstacle square exactly once. We will backtrack whenever we hit a dead end or revisit a square.

Time Complexity and Space Complexity Analysis​

  • Time Complexity: O(4m×n)O(4^{m \times n}), where m×nm \times n is the total number of cells. This is because, in the worst case, we might explore all possible paths.
  • Space Complexity: O(m×n)O(m \times n), for the recursion stack and the visited array.

Code​

C++​

class Solution {
public:
int uniquePathsIII(vector<vector<int>>& grid) {
int rows = grid.size();
int cols = grid[0].size();
int emptySquares = 1; // including the starting point
int startX, startY;

for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
if (grid[i][j] == 0) {
++emptySquares;
} else if (grid[i][j] == 1) {
startX = i;
startY = j;
}
}
}

return dfs(grid, startX, startY, emptySquares);
}

private:
int dfs(vector<vector<int>>& grid, int x, int y, int emptySquares) {
if (x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size() || grid[x][y] == -1) {
return 0;
}
if (grid[x][y] == 2) {
return emptySquares == 0 ? 1 : 0;
}

grid[x][y] = -1;
int paths = dfs(grid, x + 1, y, emptySquares - 1) +
dfs(grid, x - 1, y, emptySquares - 1) +
dfs(grid, x, y + 1, emptySquares - 1) +
dfs(grid, x, y - 1, emptySquares - 1);
grid[x][y] = 0;

return paths;
}
};

Python​

class Solution:
def uniquePathsIII(self, grid: List[List[int]]) -> int:
rows, cols = len(grid), len(grid[0])
empty_squares = 1 # including the starting point
start_x, start_y = 0, 0

for i in range(rows):
for j in range(cols):
if grid[i][j] == 0:
empty_squares += 1
elif grid[i][j] == 1:
start_x, start_y = i, j

def dfs(x, y, empty_squares):
if x < 0 or x >= rows or y < 0 or y >= cols or grid[x][y] == -1:
return 0
if grid[x][y] == 2:
return 1 if empty_squares == 0 else 0

grid[x][y] = -1
paths = (dfs(x + 1, y, empty_squares - 1) +
dfs(x - 1, y, empty_squares - 1) +
dfs(x, y + 1, empty_squares - 1) +
dfs(x, y - 1, empty_squares - 1))
grid[x][y] = 0

return paths

return dfs(start_x, start_y, empty_squares)

Java​

class Solution {
public int uniquePathsIII(int[][] grid) {
int rows = grid.length;
int cols = grid[0].length;
int emptySquares = 1; // including the starting point
int startX = 0, startY = 0;

for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == 0) {
emptySquares++;
} else if (grid[i][j] == 1) {
startX = i;
startY = j;
}
}
}

return dfs(grid, startX, startY, emptySquares);
}

private int dfs(int[][] grid, int x, int y, int emptySquares) {
if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] == -1) {
return 0;
}
if (grid[x][y] == 2) {
return emptySquares == 0 ? 1 : 0;
}

grid[x][y] = -1;
int paths = dfs(grid, x + 1, y, emptySquares - 1) +
dfs(grid, x - 1, y, emptySquares - 1) +
dfs(grid, x, y + 1, emptySquares - 1) +
dfs(grid, x, y - 1, emptySquares - 1);
grid[x][y] = 0;

return paths;
}
}