每日一题：不同路径问题

题目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

分析

回溯问题，先找到起始方格坐标和结束方格坐标，把起始坐标作为回溯的起点，之后就开始上下左右四个方向移动，这里将走过的节点值置3，表明已经走过，当前节点回溯后记得恢复状态，原来是0回溯后恢复为0，原来是2的回溯后恢复为2，当节点坐标和终点坐标相同时，判断是不是每个无障碍的方格都已经通过，如果通过则结果加1，见代码：

代码

class Solution {
public:
    int uniquePathsIII(vector<vector<int>>& grid) {
        if (!GetStartIndex(grid, start_r, start_c)) return 0;
        if (!GetEndIndex(grid, end_r, end_c)) return 0;
        BackTrace(grid, start_r, start_c);
        return ret;
    }

    void BackTrace(vector<vector<int>>& grid, int r, int c) {
        if (r == end_r && c == end_c && IsWalkAllPath(grid)) {
            ret += 1;
            return;
        }
        int row = grid.size();
        int col = grid[0].size();
        for (int k = 0; k < 4; ++k) {
            int i = r + direction_i[k];
            int j = c + direction_j[k];
            if (i < 0 || j < 0 || i >= row || j >= col) continue;
            if (grid[i][j] == 0 || grid[i][j] == 2) {
                int tem = grid[i][j];
                grid[i][j] = used;
                BackTrace(grid, i, j);
                grid[i][j] = tem;
            }
        }
    }

    bool IsWalkAllPath(vector<vector<int>>& grid) {
        int r = grid.size();
        int c = grid[0].size();
        for (auto v : grid) {
            for (auto i : v) {
                if (i == 0) return false;
            }
        }
        return true;
    }

    int start_r = 0;
    int start_c = 0;
    int end_r = 0;
    int end_c = 0;
    int ret = 0;
    int direction_i[4] = {1, -1, 0, 0};
    int direction_j[4] = {0, 0, 1, -1};
    int used = 3;

    bool GetStartIndex(vector<vector<int>>& grid, int &r, int &c) {
        return GetValueIndex(grid, 1, r, c);
    }

    bool GetEndIndex(vector<vector<int>>& grid, int &r, int &c) {
        return GetValueIndex(grid, 2, r, c);
    }

    bool GetValueIndex(vector<vector<int>>& grid, int value, int &r, int &c) {
        int row = grid.size();
        int col = grid[0].size();
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                if (grid[i][j] == value) {
                    r = i;
                    c = j;
                    return true;
                }
            }
        }
        return false;
    }
};