Algorithm
Problem Name: 980. Unique Paths III
Problem Link: https://leetcode.com/problems/unique-paths-iii/
You are given an m x n integer array grid where grid[i][j] could be:
1representing the starting square. There is exactly one starting square.2representing the ending square. There is exactly one ending square.0representing empty squares we can walk over.-1representing 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: grid = [[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: grid = [[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: grid = [[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.
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 201 <= m * n <= 20-1 <= grid[i][j] <= 2- There is exactly one starting cell and one ending cell.
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
int[][] dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
public int uniquePathsIII(int[][] grid) {
if (grid.length == 0 || grid[0].length == 0) {
return 0;
}
int rows = grid.length;
int cols = grid[0].length;
int startX = 0;
int startY = 0;
int numOfEmptySquare = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == 1) {
startX = i;
startY = j;
}
if (grid[i][j] == 0) {
numOfEmptySquare++;
}
}
}
int[] count = {0};
helper(grid, startX, startY, numOfEmptySquare, 0, new boolean[rows][cols], count);
return count[0];
}
private void helper(
int[][] grid, int startX, int startY, int numOfEmptySquare,
int currEmptySquare, boolean[][] visited, int[] count
) {
if (startX < 0 || startX >= grid.length || startY < 0 || startY >= grid[0].length || grid[startX][startY] == -1 || visited[startX][startY]) {
return;
}
if (grid[startX][startY] == 2) {
if (currEmptySquare == numOfEmptySquare) {
count[0]++;
}
return;
}
visited[startX][startY] = true;
for (int[] dir : dirs) {
helper(grid, startX + dir[0], startY + dir[1], numOfEmptySquare, (grid[startX][startY] == 0 ? currEmptySquare + 1 : currEmptySquare), visited, count);
}
visited[startX][startY] = false;
}
}
Input
grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output
2
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const uniquePathsIII = function(grid) {
const obj = {
eNum: 1,
res: 0,
rows: grid.length,
dirs: [[-1, 0], [1, 0], [0, -1], [0, 1]],
sr: 0,
sc: 0,
er: 0,
ec: 0
}
if (obj.rows === 0) return 0
obj.cols = grid[0].length
for (let i = 0; i < obj.rows; i++) {
for (let j = 0; j < obj.cols; j++) {
if (grid[i][j] === 0) obj.eNum++
else if (grid[i][j] === 1) (obj.sr = i), (obj.sc = j)
else if (grid[i][j] === 2) (obj.er = i), (obj.ec = j)
}
}
bt(grid, obj.sr, obj.sc, obj)
return obj.res
}
function bt(grid, x, y, obj) {
if (x < 0 || x >= obj.rows || y < 0 || y >= obj.cols || grid[x][y] < 0) return
if (x === obj.er && y === obj.ec) {
if (obj.eNum === 0) obj.res++
return
}
grid[x][y] = -2
obj.eNum--
for (let dir of obj.dirs) {
bt(grid, x + dir[0], y + dir[1], obj)
}
obj.eNum++
grid[x][y] = 0
}
Input
grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output
2
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def uniquePathsIII(self, grid: List[List[int]]) -> int:
def dfs(i, j, visited):
if grid[i][j] == 2:
self.walks += visited == self.visit
return
for x, y in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
if 0 <= x < m and 0 <= y < n and grid[x][y] != -1:
grid[i][j] -= 1
dfs(x, y, visited + 1)
grid[i][j] += 1
m, n = len(grid), len(grid[0])
self.visit = m * n - sum(c == -1 for row in grid for c in row)
self.walks = 0
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
grid[i][j] -= 1
dfs(i, j, 1)
return self.walks
Input
grid = [[1,0,0,0],[0,0,0,0],[0,0,0,2]]
Output
4
#4 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _0980_UniquePathsIII
{
private readonly (int dr, int dc)[] direction = new (int dr, int dc)[4] { (1, 0), (-1, 0), (0, 1), (0, -1) };
private int count = 0;
public int UniquePathsIII(int[][] grid)
{
int rows = grid.Length, cols = grid[0].Length;
int nonObstacles = 0, startRow = -1, startCol = -1;
for (int row = 0; row < rows; row++)
for (int col = 0; col < cols; col++)
{
int cell = grid[row][col];
if (cell >= 0)
nonObstacles += 1;
if (cell == 1)
{
startRow = row;
startCol = col;
}
}
Backtrack(grid, startRow, startCol, nonObstacles);
return this.count;
}
private void Backtrack(int[][] grid, int row, int col, int nonObstacles)
{
if (grid[row][col] == 2 && nonObstacles == 1)
{
this.count++;
return;
}
int rows = grid.Length, cols = grid[0].Length;
int temp = grid[row][col];
grid[row][col] = -2;
nonObstacles -= 1;
foreach ((int dr, int dc) in direction)
{
int newRow = row + dr;
int newCol = col + dc;
if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && grid[newRow][newCol] >= 0)
Backtrack(grid, newRow, newCol, nonObstacles);
}
grid[row][col] = temp;
}
}
}
Input
grid = [[1,0,0,0],[0,0,0,0],[0,0,0,2]]
Output
4