在二维网格 grid 上，有 4 种类型的方格：
- 1 表示起始方格。且只有一个起始方格。
- 2 表示结束方格，且只有一个结束方格。
- 0 表示我们可以走过的空方格。
- -1 表示我们无法跨越的障碍。
返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目。
每一个无障碍方格都要通过一次，但是一条路径中不能重复通过同一个方格。
1. 回溯法
class Solution {
public:
int dir[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
int uniquePathsIII(vector<vector<int>>& grid) {
int m = grid.size(); int n = grid[0].size();
int ox,oy;
int target = 0;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
if(grid[i][j]==0) target++;
else if(grid[i][j]==1) target++,ox=i,oy=j;
function<int(int,int,int)> dfs = [&](int x,int y,int cnt)->int{
if(grid[x][y]==2){
if(cnt==target) return 1;//到达目的地
return 0;//错误路径
}
int res = 0;
grid[x][y] = -1;//做选择，不可通行
for(int i=0;i<4;i++){//遍历四个方向
int nx = x + dir[i][0];
int ny = y + dir[i][1];
if(nx<0||nx>=m||ny<0||ny>=n||grid[nx][ny]==-1) continue;//无法通行
res += dfs(nx,ny,cnt+1);
}
grid[x][y] = 0;//撤销选择，放开道路
return res;
};
return dfs(ox,oy,0);
}
};