不同路径 III【LC980】
在二维网格
grid上，有 4 种类型的方格：
1表示起始方格。且只有一个起始方格。2表示结束方格，且只有一个结束方格。0表示我们可以走过的空方格。-1表示我们无法跨越的障碍。- 返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目**。**
每一个无障碍方格都要通过一次，但是一条路径中不能重复通过同一个方格。
- 思路从起点出发，寻找经过所有空格到达终点的路径个数
- 首先遍历一遍矩阵，找到起点位置、终点位置以及空格数量
- 然后通过dfs+回溯的方式，寻找有效路径，为了防止重复遍历，还需要使用
visit数组记录每个结点的访问状态
实现
- 回溯函数模板返回值以及参数
loc（当前位置）left（当前剩余的空格数量）- 全局变量：
grid、visit - 返回值 int：从当前位置当终点的路径个数
- 回溯函数终止条件
- 到达终点时返回，如果剩余空格个数为0，返回1；反之，返回0
- 回溯搜索的遍历过程
- 首先判断当前位置是否访问过【记忆化，优化不明显】
- 然后判断是否到达终点
- 再向四个方向进行移动，需要判断坐标是否合法、是否被访问过、是否是障碍物
class Solution { int m, n; boolean[][] visit; int[][] grid; int[] dir = {0, 1, 0, -1, 0}; int[] end; int[][] dp; public int uniquePathsIII(int[][] grid) { this.m = grid.length; this.n = grid[0].length; this.visit = new boolean[m][n]; this.grid = grid; int[] start = new int[2]; this.end = new int[2]; this.dp = new int[m][n]; int total = 0; for (int i = 0; i < m; i++){ Arrays.fill(dp[i], -1); for (int j = 0; j < n; j++){ if (grid[i][j] == 1){ start[0] = i; start[1] = j; }else if (grid[i][j] == 2){ end[0] = i; end[1] = j; total++; }else if (grid[i][j] == 0){ total++; } } } visit[start[0]][start[1]] = true; return dfs(start, total); } public int dfs(int[] loc, int left){ if (dp[loc[0]][loc[1]] != -1) return dp[loc[0]][loc[1]]; if (loc[0] == end[0] && loc[1] == end[1]){ if (left == 0){ return 1; }else{ return 0; } } int res = 0; for (int i = 0; i < 4; i++){ int[] u = {loc[0] + dir[i], loc[1] + dir[i + 1]}; if (u[0] >= 0 && u[0] < m && u[1] >= 0 && u[1] < n && !visit[u[0]][u[1]] && grid[u[0]][u[1]] != -1){ visit[u[0]][u[1]] = true; res += dfs(u, left - 1); visit[u[0]][u[1]] = false; } } return res; } }
