class Solution {
private int rows, cols;
private int[][] directions = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
private int totalPaths = 0;
public int uniquePathsIII(int[][] grid) {
rows = grid.length;
cols = grid[0].length;
int startX = 0, startY = 0, emptyCells = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == 1) {
startX = r;
startY = c;
} else if (grid[r][c] == 0) {
emptyCells++;
}
}
}
dfs(grid, startX, startY, emptyCells + 1);
return totalPaths;
}
private void dfs(int[][] grid, int x, int y, int remainingCells) {
if (x < 0 || y < 0 || x >= rows || y >= cols || grid[x][y] == -1) {
return;
}
if (grid[x][y] == 2) {
if (remainingCells == 0) {
totalPaths++;
}
return;
}
int temp = grid[x][y];
grid[x][y] = -1;
for (int[] direction : directions) {
int newX = x + direction[0];
int newY = y + direction[1];
dfs(grid, newX, newY, remainingCells - 1);
}
grid[x][y] = temp;
}
}
𝗢𝗽𝗲𝗻 𝘁𝗼 𝗨𝗽𝗱𝗮𝘁𝗲𝘀 𝗮𝗻𝗱 𝗦𝘂𝗴𝗴𝗲𝘀𝘁𝗶𝗼𝗻𝘀
Top comments (0)