LeetCode 980. 不同路径 III

作者:Choi Yang

更新于:6 个月前

字数统计:1.4k 字

阅读时长:6 分钟

阅读量:

题目描述

在二维网格 grid 上，有 4 种类型的方格：

1 表示起始方格。且只有一个起始方格。 2 表示结束方格，且只有一个结束方格。 0 表示我们可以走过的空方格。 -1 表示我们无法跨越的障碍。返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目。

每一个无障碍方格都要通过一次，但是一条路径中不能重复通过同一个方格。

示例 1：

javascript

输入：[[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
输出：2
解释：我们有以下两条路径：
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)

示例 2：

javascript

输入：[[1,0,0,0],[0,0,0,0],[0,0,0,2]]
输出：4
解释：我们有以下四条路径：
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)

示例 3：

javascript

输入：[[0,1],[2,0]]
输出：0
解释：
没有一条路能完全穿过每一个空的方格一次。
请注意，起始和结束方格可以位于网格中的任意位置。

提示：

javascript

1 <= grid.length * grid[0].length <= 20;

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/unique-paths-iii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

回溯算法，不过这道题需要我们走完所有空格，所以我们起初遍历的时候需要统计一下空格的数目，然后还有一个注意点就是重点也算是可走的路径的一个点，也需要统计进去，所以代码 cnt 值初始化为 1

接下来就是回溯过程了，写了一个 check 函数，进行简单判断剪枝，然后就是往四个方向搜，每走一个格子就将当前格子设置为障碍（即 -1），然后搜索完后，回溯时，需要将障碍重设置为空格。

javascriptcppjavapython

javascript

/**
 * @param {number[][]} grid
 * @return {number}
 */
var uniquePathsIII = function (grid) {
  let cnt = 1; // 统计地图中可走的方格个数，包括终点，故初始值为1
  let sx, sy; // 记录起点坐标
  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[0].length; j++) {
      if (grid[i][j] === 1) {
        sx = i;
        sy = j;
      } else if (grid[i][j] === 0) {
        cnt++;
      }
    }
  }
  return dfs(sx, sy, cnt, grid);
};
// 剪枝条件
let check = (sx, sy, grid) => {
  if (sx < 0 || sx >= grid.length || sy < 0 || sy >= grid[0].length || grid[sx][sy] == -1)
    return false;
  return true;
};

let dfs = (sx, sy, cnt, grid) => {
  if (!check(sx, sy, grid)) return 0;
  if (grid[sx][sy] === 2) {
    // 走到终点时，也要判断一下当前所有空格是否走完
    return cnt === 0 ? 1 : 0;
  }
  let res = 0;
  grid[sx][sy] = -1; //走过的空格进行标记，设置为障碍即可
  res += dfs(sx + 1, sy, cnt - 1, grid); // 四个方向进行搜索
  res += dfs(sx, sy + 1, cnt - 1, grid);
  res += dfs(sx - 1, sy, cnt - 1, grid);
  res += dfs(sx, sy - 1, cnt - 1, grid);
  grid[sx][sy] = 0; // 回溯过程，不影响后续dfs
  return res;
};

cpp

class Solution {
public:
    int uniquePathsIII(vector<vector<int>>& grid) {
        int cnt = 1; // 统计地图中可走的方格个数，包括终点，故初始值为1
        int sx, sy; // 记录起点坐标
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == 1) {
                    sx = i;
                    sy = j;
                } else if (grid[i][j] == 0) {
                    cnt++;
                }
            }
        }
        return dfs(sx, sy, cnt, grid);
    }
    // 剪枝条件
    bool check(int sx, int sy, vector<vector<int>>& grid) {
        if (sx < 0 || sx >= grid.size() || sy < 0 || sy >= grid[0].size() || grid[sx][sy] == -1) return false;
        return true;
    }
    int dfs(int sx, int sy, int cnt, vector<vector<int>>& grid) {
        if (!check(sx, sy, grid)) return 0;
        if (grid[sx][sy] == 2) { // 走到终点时，也要判断一下当前所有空格是否走完
            return cnt == 0 ? 1 : 0;
        }
        int res = 0;
        grid[sx][sy] = -1; //走过的空格进行标记，设置为障碍即可
        res += dfs(sx + 1, sy, cnt - 1, grid); // 四个方向进行搜索
        res += dfs(sx, sy + 1, cnt - 1, grid);
        res += dfs(sx - 1, sy, cnt - 1, grid);
        res += dfs(sx, sy - 1, cnt - 1, grid);
        grid[sx][sy] = 0; // 回溯过程，不影响后续dfs
        return res;
    }
};

java

class Solution {
    int res = 0;
    int cnt = 1;
    int sx, sy;
    public int uniquePathsIII(int[][] grid) {
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    sx = i;
                    sy = j;
                } else if (grid[i][j] == 0) {
                    cnt++;
                }
            }
        }
        dfs(sx, sy, grid);
        return res;
    }
    public void dfs(int sx, int sy, int[][] grid) {
        if (sx < 0 || sx >= grid.length || sy < 0 || sy >= grid[0].length || grid[sx][sy] == -1) return;
        if (grid[sx][sy] == 2) {
            res += cnt == 0 ? 1 : 0;
            return;
        }
        grid[sx][sy] = -1;
        cnt--;
        dfs(sx + 1, sy, grid);
        dfs(sx, sy + 1, grid);
        dfs(sx - 1, sy, grid);
        dfs(sx, sy - 1, grid);
        grid[sx][sy] = 0;
        cnt++;
    }
}

python

class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        cnt = 1
        sx, sy = 0, 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    sx, sy = i, j
                elif grid[i][j] == 0:
                    cnt += 1
        def dfs(sx, sy, cnt):
            if sx < 0 or sx >= len(grid) or sy < 0 or sy >= len(grid[0]) or grid[sx][sy] == -1:
                return 0
            if grid[sx][sy] == 2:
                return 1 if cnt == 0 else 0
            grid[sx][sy] = -1
            cnt -= 1
            res = dfs(sx + 1, sy, cnt) + dfs(sx, sy + 1, cnt) + dfs(sx - 1, sy, cnt) + dfs(sx, sy - 1, cnt)
            grid[sx][sy] = 0
            cnt += 1
            return res
        return dfs(sx, sy, cnt)

javascript

学如逆水行舟，不进则退

Contributors

Choi Yang

LeetCode 980. 不同路径 III ​

题目描述 ​

解题思路 ​

Contributors ​

LeetCode 980. 不同路径 III

题目描述

解题思路

Contributors