每日OJ题_DFS爆搜深搜回溯剪枝⑧

每日OJ题_DFS爆搜深搜回溯剪枝⑧_力扣980. 不同路径 III

力扣980. 不同路径 III

解析代码

力扣980. 不同路径 III

980. 不同路径 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

class Solution {
public:
    int uniquePathsIII(vector<vector<int>>& grid) {

    }
};

解析代码

可以用DP解决，但是这道题的DP是竞赛级别的，所以这里用爆搜的方法：对于四个方向，我们可以定义一个二维数组 next ，大小为 4 ，每一维存储四个方向的坐标偏移量。题目要求到达目标位置时所有无障碍方格都存在路径中，我们可以定义一个变量记录 num 当前状态中剩余的未走过的无障碍方格个数，则当我们走到目标地点时只需要判断 num 是否为 0 即可。在移动时需要判断是否越界。

class Solution {
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    bool vis[20][20];
    int m, n, ret, step = 2; // step是总共要走的步数，算上终点和起点

public:
    int uniquePathsIII(vector<vector<int>>& grid) {
        m = grid.size(), n = grid[0].size();
        int x = 0, y = 0;
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(grid[i][j] == 0)
                    ++step; // 遇到一个0，要走的步数+1
                else if(grid[i][j] == 1)
                    x = i, y = j; // 记录起始位置
            }
        }
        vis[x][y] = true;
        dfs(grid, x, y, 1); // 起点算一个步数了
        return ret;
    }

    void dfs(vector<vector<int>>& grid, int i, int j, int cnt)
    {
        if(grid[i][j] == 2)
        {
            if(step == cnt)
                ++ret;
            return;
        }
        for(int k = 0; k < 4; ++k)
        {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] != -1 && !vis[x][y])
            {
                vis[x][y] = true;
                dfs(grid, x, y, cnt + 1);
                vis[x][y] = false;
            }
        }
    }
};