题目描述
在二维网格 grid 上，有 4 种类型的方格：
1表示起始方格。且只有一个起始方格。2表示结束方格，且只有一个结束方格。0表示我们可以走过的空方格。-1表示我们无法跨越的障碍。 返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目，每一个无障碍方格都要通过一次。
示例 1：
输入：[[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
输出： 2
解释： 我们有以下两条路径：
- (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)
示例 2：
输入：[[1,0,0,0],[0,0,0,0],[0,0,0,2]]
输出： 4
解释： 我们有以下四条路径：
- (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)
示例 3：
输入：[[0,1],[2,0]]
输出： 0
解释： 没有一条路能完全穿过每一个空的方格一次。
请注意，起始和结束方格可以位于网格中的任意位置。
来源：LeetCode
思路
典型的深度优先搜索题目。
我们找到起始方格，在此方格向任意方向走，走过的地方记为-1，即不能再走。当遇到 2 时，判断是否所有方格已经没有 0 了，若是则这是一个有效路径。
解法
// 检查是否已经走完所有空方格
const check = grid => {
for (let i = 0; i < grid.length; i++) {
for (let j = 0; j < grid[0].length; j++) {
if (grid[i][j] === 0) return false;
}
}
return true;
};
// 找到起始方格
const findStart = grid => {
for (let i = 0; i < grid.length; i++) {
for (let j = 0; j < grid[0].length; j++) {
if (grid[i][j] === 1) return [i, j];
}
}
};
const copyGrid = grid => grid.map(i => [...i]);
/**
* @param {number[][]} grid
* @return {number}
*/
const uniquePathsIII = grid => {
let result = 0;
const [row, col] = findStart(grid);
const walk = ({ i, j }, grid) => {
if (grid[i][j] === 2) {
check(grid) && result++;
return;
}
const newGrid = copyGrid(grid);
newGrid[i][j] = -1;
// 尝试向上走
if (i - 1 >= 0 && grid[i - 1][j] !== -1) {
walk({ i: i - 1, j }, newGrid);
}
// 尝试向下走
if (i + 1 < grid.length && grid[i + 1][j] !== -1) {
walk({ i: i + 1, j }, newGrid);
}
// 尝试向左走
if (j - 1 >= 0 && grid[i][j - 1] !== -1) {
walk({ i, j: j - 1 }, newGrid);
}
// 尝试向右走
if (j + 1 < grid[0].length && grid[i][j + 1] !== -1) {
walk({ i, j: j + 1 }, newGrid);
}
};
walk({ i: row, j: col }, grid);
return result;
};