题目描述

在一个二维的网格上，有四种格子：

1. 1 表示起始格子。仅有一个起始格子。
2. 2 表示终止格子。仅有一个终止格子。
3. 0 表示空格子，我们可以通过。
4. -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
解释：
没有路径可以通过每个空格子仅一次。
注意到起始格子和终止格子可以在网格中的任意位置。

注意

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

算法

(递归回溯) $O(4^{nm})$

1. 从起点开始枚举向四个方向行走，如果行走不通，则回溯。如果能走通，则更新现场；
2. 到了终点后，判断是否还有没有走到的格子，如果没有了，则答案加一，然后回溯恢复现场。

时间复杂度

• 每个格子都有 4 种选择，故时间复杂度为 $O(4^{nm})$。

空间复杂度

• 递归需要系统栈，最坏情况下需要 $nm$ 大小的栈，故空间复杂度为 $O(nm)$。

C++ 代码

class Solution {
public:
    int dx[4] = {0, 1, 0, -1};
    int dy[4] = {1, 0, -1, 0};
    pair<int, int> S, T;
    int n, m, ans;

    void dfs(vector<vector<int>>& grid, int x, int y) {
        if (x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == 3 || grid[x][y] == -1)
            return;
        grid[x][y] = 3;
        if (x == T.first && y == T.second) {
            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                    if (grid[i][j] == 0) {
                        grid[x][y] = 0;
                        return;
                    }

            ans++;
            grid[x][y] = 0;
            return;
        }

        for (int i = 0; i < 4; i++) {
            int tx = x + dx[i], ty = y + dy[i];
            dfs(grid, tx, ty);
        }
        grid[x][y] = 0;
    }

    int uniquePathsIII(vector<vector<int>>& grid) {
        n = grid.size();
        m = grid[0].size();
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    S = make_pair(i, j);
                    grid[i][j] = 0;
                }
                else if (grid[i][j] == 2) {
                    T = make_pair(i, j);
                    grid[i][j] = 0;
                }
            }
        ans = 0;
        dfs(grid, S.first, S.second);
        return ans;
    }
};