980. Unique Paths III

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. 1 <= grid.length * grid[0].length <= 20

这道题是 Unique Path 系列的第三道,虽说是拓展,但是说实话,博主感觉跟前两道 Unique Paths IIUnique 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

类似题目:

Sudoku Solver

Unique Paths II

Unique Paths

Word Search II

参考资料:

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 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation