980. Unique Paths III

置顶

Created At : 2023-10-28 15:14

Count:1.2k Views 👀 :

On a 2-dimensional grid, there are 4 types of squares:

1 represents the starting square. There is exactly one starting square.
2 represents the ending square. There is exactly one ending square.
0 represents empty squares we can walk over.
-1 represents 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: [[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: [[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: [[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.

Note:

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

这道题是 Unique Path 系列的第三道，虽说是拓展，但是说实话，博主感觉跟前两道 Unique Paths II 和 Unique Paths 的差异还是挺大的，那两道都是要用动态规划来做，而这道却是更传统的迷宫遍历的做法。这里给了一个二维数组 grid，里面有四种状态，1表示起点，2表示终点，0表示通路，-1 表示障碍物不能通过。现在让返回从起点到终点，并且经过每个可通过的位置1次的不同路径的个数。现在来分析，虽说是要从起点到终点，但是每个位置都要经过一次（障碍物除外），就是说即便起点终点挨在一起，还是要整个图跑一圈再回来才行。不过本质还是遍历迷宫的问题，一般遍历迷宫都有广度优先遍历 BFS 和深度优先遍历 DFS 两种选择，但是这里 BFS 就不太适用了，因为它是从起点开始一圈一圈往外扩散，直到到达终点位置，适用于求起点到终点的最短路径的问题。这里可以用 DFS 来做，另外，如果确保当前的路径正好经过每个位置1次，只经过1次好办，可以通过修改位置上的状态，标记已经走过的位置，就不会经过同一个位置两次。接下来看如何保证经过所有的位置，所有能经过的位置都是0，则把数组中所有的0的个数统计出来，别忘了再加上终点的位置，因为也能到达。这样每走一步，就把目标步数减1，只要到达终点位置的时候，目标步数正好为0，就说明这条路径是符合题意的。好了，思路理清了，就来写代码吧，先遍历一遍数组，找出起点位置，和统计出目标步数。然后调用递归函数，在递归函数中，首先判断当前位置是否越界，已经当前位置的状态值是否小于0（访问过的位置标被记为 -2），是的话就直接返回。否则将当前位置标记为 -2，并且目标值减1，然后对周围四个位置调用递归函数，之后别忘记了恢复状态，状态标记0，目标步数加1，参见代码如下：

class Solution {
public:
    int uniquePathsIII(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size(), x0 = 0, y0 = 0, target = 1, res = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    x0 = i; y0 = j;
                } else if (grid[i][j] == 0) {
                    ++target;
                }
            }
        }
        helper(grid, target, x0, y0, res);
        return res;
    }
    void helper(vector<vector<int>>& grid, int& target, int i, int j, int& res) {
        int m = grid.size(), n = grid[0].size();
        if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] < 0) return;
        if (grid[i][j] == 2) {
            if (target == 0) ++res;
            return;
        }
        grid[i][j] = -2;
        --target;
        helper(grid, target, i + 1, j, res);
        helper(grid, target, i - 1, j, res);
        helper(grid, target, i, j + 1, res);
        helper(grid, target, i, j - 1, res);
        grid[i][j] = 0;
        ++target;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/980

类似题目：

参考资料：

https://leetcode.com/problems/unique-paths-iii/

https://leetcode.com/problems/unique-paths-iii/discuss/221941/C%2B%2B-brute-force-DFS

https://leetcode.com/problems/unique-paths-iii/discuss/221946/JavaPython-Brute-Force-Backtracking

LeetCode All in One 题目讲解汇总(持续更新中…)