[LC]980. 不同路径 III

🚩传送门：力扣题目

题目

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

• 表示起始方格。且只有一个起始方格。
• 表示结束方格，且只有一个结束方格。
• 表示我们可以走过的空方格。
• 表示我们无法跨越的障碍。

返回在四个方向（ 上、下、左、右 ）上行走时，从起始方格到结束方格的不同路径的数目。

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

示例 1：

输入：[[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)

解题思路：深搜

让我们尝试遍历每一个 方格，并在走过的方格里留下一个障碍。回溯的时候，我们要删除那些自己留下的障碍。
深搜所有的可能路径，对到达终点的路径判断是否已经全部路过了每一个 方格（即数组中不存在 方格），满足条件的全局变量 加 。

复杂度分析

时间复杂度：，其中是这个二维网格行与列的大小。

空间复杂度：

官方代码

class Solution {
    int res;
    public int uniquePathsIII(int[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        res = 0;
        // 找起点位置开始dfs
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 1) {
                    dfs(grid, i, j);
                    return res;
                }
            }
        }
        return res;
    }
    private void dfs(int[][] grid, int i, int j) {
        // 边界合法性检查
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[i].length) return;
        // 判断能否跨越
        if (grid[i][j] == -1) return;
        // 遇到终点,判断当前路径是否满足要求
        if (grid[i][j] == 2) {
            // 检查是否还有未走的空格
            for (int k = 0; k < grid.length; k++) {
                for (int l = 0; l < grid[k].length; l++) {
                    if (grid[k][l] == 0) return;
                }
            }
            res++;
            return;
        }
        // 对可行点(i,j)标记访问
        grid[i][j] = -1;
        // 定义四向搜索
        int[][] dir = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        for (int k = 0; k < dir.length; k++) {
            dfs(grid,i+dir[k][0],j+dir[k][1]);
        }
        // 四向搜索完成,取消标记
        grid[i][j] = 0;
    }
}