题目描述
在二维网格 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)
解题思路
这道题与上一题不同之处在于，这道题起始点和终止点的位置不确定，而且这道题明确要求所有空位点必须经过一次，且最终点落脚到终止点。
题目判断是否所有点均走过可以使用一个变量来记录，事先保存好所有可以走的点的总数（包括起始点，终止点可空位点），然后使用回溯方法，当到达终点时，判断走过的点总是是否等于预先保存的那个数，如果是，则满足条件
class Solution(object):def uniquePathsIII(self, grid):""":type grid: List[List[int]]:rtype: int"""cnt = 0 #无障碍方格总数start_x = start_y = 0self.end_x = self.end_y = 0m, n = len(grid), len(grid[0])for i in range(m):for j in range(n):if grid[i][j] == 1:start_x = istart_y = jcnt += 1elif grid[i][j] == 2:self.end_x = iself.end_y = jcnt += 1elif grid[i][j] == 0:cnt += 1self.res = 0grid[start_x][start_y] = -1self.dfs(grid, m, n, start_x, start_y, cnt, 0)return self.resdef dfs(self, grid, m, n, x, y, cnt, step):if x == self.end_x and y == self.end_y:if step == cnt - 1:self.res += 1returnfor nx, ny in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] != -1:temp = grid[nx][ny]grid[nx][ny] = -1self.dfs(grid, m, n, nx, ny, cnt, step + 1)grid[nx][ny] = tempS = Solution() print(S.uniquePathsIII([[1,0,0,0],[0,0,0,0],[0,0,2,-1]]))
这里首先先保存起始点和终止点的下标，并且记录所有可以走的点的总数（这里0，1， 2均可），没每走过一个点，就将该点置为-1，方便后续操作，同一层dfs执行完后需要将这个点再变回来（这点很重要，对应于grid[nx][ny] = temp这是回溯的基本框架）。