题目

在二维网格 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. 初始位置从哪里开始
2. 首先要计算出我到终点的时候走过多少步能走满整张表格，初始位置也要算
3. 题目需要我们找到所有能够完成的路径数目，使用回溯
4. 回溯的时候需要使用记录表，记录自己走过的路径。如果走过了不需要再走

代码

class Solution {
    private int result = 0;
    public int uniquePathsIII(int[][] grid) {
        int count = 0;
        int m = grid.length;
        int n = grid[0].length;
        // 找出初始开始位置
        int x = 0;
        int y = 0;
        boolean[][] memo = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    count++;
                } else if (grid[i][j] == 1) {
                    x = i;
                    y = j;
                    count++;
                }
            }
        }
        dfs(grid,memo, x, y, count, 0);
        return result;
    }

    /**
     * @param grid  表格
     * @param memo  记录表
     * @param x     列
     * @param y     行
     * @param count 空白格数量
     * @param sum   路过的空白格数量+开始格子
     */
    private void dfs(int[][] grid,boolean[][] memo, int x, int y, int count, int sum) {
        // 这种情况就返回
        if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] == -1 || memo[x][y]) {
            return;
        }
        // 和空白格+开始格子数量相等，则保存
        if (grid[x][y] == 2 && sum == count) {
            result++;
            return;
        }
        memo[x][y] = true;
        dfs(grid,memo, x - 1, y, count, sum + 1);
        dfs(grid,memo, x + 1, y, count, sum + 1);
        dfs(grid,memo, x, y - 1, count, sum + 1);
        dfs(grid,memo, x, y + 1, count, sum + 1);
        memo[x][y] = false;
    }
}