题目

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

1 表示起始方格。且只有一个起始方格。
2 表示结束方格，且只有一个结束方格。
0 表示我们可以走过的空方格。
-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)

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

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

解答 & 代码

递归回溯

class Solution {
private:
    // DFS 递归回溯
    // row、col 是当前坐标，nullCnt 是 grid 中 1、0 的数量（即合法路径除去终点的长度）
    // visitedCnt 是当前路径的长度，pathCnt 是合法路径数
    void backtrace(vector<vector<int>>& grid, int row, int col, int nullCnt, int visitedCnt, int& pathCnt)
    {
        int rows = grid.size();
        int cols = grid[0].size();
        // 递归结束条件
        if(row < 0 || row >= rows || col < 0 || col >= cols)    // 若坐标越界，直接返回
            return;
        if(grid[row][col] == 2)                                    // 若到达终点
        {
            if(nullCnt == visitedCnt)                            // 如果是合法路径，则 pathCnt +1
                ++pathCnt;
            return;
        }
        if(grid[row][col] != 1 && grid[row][col] != 0)            // 若当前格子是障碍（-1），直接返回
            return;

        // 选择
        ++visitedCnt;                // 当前路径长度 +1（访问了当前格子）
        grid[row][col] = -1;        // 将当前格子置为 -1，代表已访问过
        // 递归回溯：上、下、左、右四个方向
        backtrace(grid, row - 1, col, nullCnt, visitedCnt, pathCnt);
        backtrace(grid, row + 1, col, nullCnt, visitedCnt, pathCnt);
        backtrace(grid, row, col - 1, nullCnt, visitedCnt, pathCnt);
        backtrace(grid, row, col + 1, nullCnt, visitedCnt, pathCnt);
        // 撤销选择
        grid[row][col] = 0;
        --visitedCnt;
    }
public:
    int uniquePathsIII(vector<vector<int>>& grid) {
        if(grid.size() == 0 || grid[0].size() == 0)
            return 0;
        int rows = grid.size();
        int cols = grid[0].size();
        int pathCnt = 0;
        int nullCnt = 0;
        int startRow = -1;
        int startCol = -1;
        // 统计 0、1 的格子数 nullCnt，以及寻找到起点坐标
        for(int i = 0; i < rows; ++i)
        {
            for(int j = 0; j < cols; ++j)
            {
                if(grid[i][j] == 1 || grid[i][j] == 0)
                    ++nullCnt;
                if(grid[i][j] == 1)
                {
                    startRow = i;
                    startCol = j;
                }
            }
        }
        if(startRow == -1 || startCol == -1)
            return 0;

        backtrace(grid, startRow, startCol, nullCnt, 0, pathCnt);
        return pathCnt;
    }
};

复杂度分析：设矩阵为 m 行 n 列

时间复杂度：合法路径包含 O(mn) 个格子（mn 个格子去掉障碍也是 O(mn) 个），在每个格子有上、下、左、右 4 种选择
空间复杂度 O(mn)：递归栈深度

执行结果：

执行结果：通过

执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户
内存消耗：6.8 MB, 在所有 C++ 提交中击败了 62.18% 的用户

hot 100

[困难] 980. 不同路径 III

题目

解答 & 代码