class Solution {
public:
int ans = 0;
void dfs(vector<vector<int>>& grid,int i,int j,int sum,int tmp,vector<vector<bool>>& hash)//tmp变量用于记录走过0位置的数量
//哈希表用于记录已经走过的位置，防止重复走过
//sum就是0的总数
{
if((i>=grid.size()||i<0||j>=grid[0].size()||j<0)||(grid[i][j] == -1 || (grid[i][j]==2&&tmp!=sum)))//剪枝操作：也就是此路不通，另寻他路
return;
if(grid[i][j]==2&&tmp==sum)//走完了所有的0位置，并且最终所处位置为2
{
ans++;
return;
}
tmp++;//每走过一个0位置tmp++
hash[i][j] = true;//将当前位置标记为 "已访问"
//上、下、左、右递归
if(i-1>=0&&!hash[i-1][j])
dfs(grid,i-1,j,sum,tmp,hash);
if(i+1<=grid.size()&&!hash[i+1][j])
dfs(grid,i+1,j,sum,tmp,hash);
if(j-1>=0&&!hash[i][j-1])
dfs(grid,i,j-1,sum,tmp,hash);
if(j+1<=grid[0].size()&&!hash[i][j+1])
dfs(grid,i,j+1,sum,tmp,hash);
hash[i][j] = false;//恢复现场
}
int uniquePathsIII(vector<vector<int>>& grid)
{
vector<vector<bool>> hash(21,vector<bool>(21));
int sum = 0;
for(int i = 0;i<grid.size();i++)
for(int j = 0;j<grid[0].size();j++)
if(!grid[i][j]) sum++;//统计0的个数
for(int i = 0;i<grid.size();i++)
{
for(int j = 0;j<grid[0].size();j++)
{
if(grid[i][j]==1)
{
dfs(grid,i,j,sum,-1,hash);//从1位置开始 dfs
break;
}
}
}
return ans;
}
};