leetcode980.不同路径III

题目

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

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

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

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

示例 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)

示例 2：

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

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

提示：

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

解答

答案所要求的路径其实就是从1到2在没有经过重复的位置的情况下长度为
【0的个数 + 2】的路径 所以其实可以直接dfs，并在dfs时记录路径的长度，当我们走到2的位置的时候，检查路径长度是否足够长即可。为了避免走重复的位置，我们在经过一个位置时将该位置标记为-1，递归函数结束时恢复为0即可。

class Solution {
public:
    int uniquePathsIII(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        // 定义四个方向的偏移量，用于遍历上、下、左、右四个方向
        short dis_x[] = {1, -1, 0, 0}, dis_y[] = {0, 0, 1, -1};
        int ret = 0;
        // x1, y1是起点（值为1）的坐标，x2, y2是终点（值为2）的坐标，len是目标长度（包括起点和终点）
        int x1, y1, x2, y2, len = 2;
        // 遍历整个矩阵，计算0的个数，以及获取1和2的坐标
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                switch (grid[i][j]) {
                    case 0: // 值为0，代表可访问的空格，目标长度len需要加1
                        ++len;
                        break;
                    case 1: // 值为1，代表起点
                        x1 = i;
                        y1 = j;
                        break;
                    case 2: // 值为2，代表终点
                        x2 = i;
                        y2 = j;
                        break;
                }
            }
        }
        
        // 定义深度优先搜索函数，使用lambda表达式
        function<void(int, int, int)> dfs = [&](int x, int y, int cnt) {
            if (x == x2 && y == y2) { // 如果当前坐标为终点坐标
                if (cnt == len) // 如果路径长度等于目标长度（包括起点和终点），则结果ret加1
                    ++ret;
                return;
            }
            grid[x][y] = -1; // 将当前坐标标记为已访问（-1）
            for (int i = 0; i < 4; ++i) { // 尝试向四个方向进行搜索
                int nx = dis_x[i] + x; // 计算下一个搜索位置的横坐标
                int ny = dis_y[i] + y; // 计算下一个搜索位置的纵坐标
                // 检查下一个搜索位置是否合法（在矩阵范围内且不为已访问的位置）
                if (nx >= 0 && ny >= 0 && nx < m && ny < n && grid[nx][ny] != -1) {
                    dfs(nx, ny, cnt + 1); // 继续向下一个位置进行搜索，路径长度加1
                }
            }
            grid[x][y] = 0; // 恢复当前坐标的值为0，表示当前位置未被访问
        };
        
        dfs(x1, y1, 1); // 调用深度优先搜索函数，初始长度为1（起点）
        return ret; // 返回结果
    }
};

---

作者：吸鼠霸王
链接：https://leetcode.cn/problems/unique-paths-iii/solutions/2212729/dfs-hui-su-by-v-me-50-l178/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。