C ++中的独特路径III
在正方形中，1是起点。恰好会有一个起始方块。
在正方形中2是终点。恰好会有一个结尾正方形。
在正方形中，0是空的正方形，我们可以走过去。
如果遇到障碍，我们不能走过正方形-1。
我们必须找到从开始方块到结束方块的4向步行次数，这些步行在每个非障碍方块上恰好走了一次。
所以，如果输入像-
那么输出将为2，因为我们有以下两条路径：(0,0)，(0,1)，(0,2)，(0,3)，(1,3)，(1,2)，(1,1)，(1,0)，(2,0)，(2,1)，(2,2)和(0,0)，(1,0)，(2,0)，（2，1），(1,1)，(0,1)，(0,2)，(0,3)，(1,3)，(1,2)，(2,2)。
为了解决这个问题，我们将遵循以下步骤-
定义一个函数dfs()，它将采用一个2D数组网格，即i，j，ex，ey，empty，
如果i，j不在grid或grid[i，j]的范围内，则等于-1，则-
返回0
如果grid[i，j]与2相同，则
如果为-1，则返回true
x：=0
（将空值减少1）
格[i，j]：=-1
对于初始化k：=0，当k<4时，更新（将k增加1），执行-
nx：=i+dir[k，0]
ny：=j+dir[k，1]
x：=x+dfs（网格，nx，ny，ex，ey，空）
（将空值增加1）
grid[i，j]：=0
返回x
从方法中执行以下操作-
空：=0
n：=行数，m：=列数
对于初始化i：=0，当i<n时，更新（将i增加1），执行-
如果grid[i，j]等于0，则
否则，当grid[i，j]等于1时，则-
否则，当grid[i，j]与2相同时，则-
（将空值增加1）
sx：=i，sy：=j
例如：=i，ey：=j
对于初始化j：=0，当j<m时，更新（将j增加1），执行-
返回dfs（grid，sx，sy，ex，ey，空）
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
class Solution {
public:
int dfs(vector<vector<int> >& grid, int i, int j, int ex, int ey,
int empty){
if (i >= grid.size() || i < 0 || j >= grid[0].size() || j < 0
|| grid[i][j] == -1)
return 0;
if (grid[i][j] == 2) {
return empty == -1;
}
int x = 0;
empty--;
grid[i][j] = -1;
for (int k = 0; k < 4; k++) {
int nx = i + dir[k][0];
int ny = j + dir[k][1];
x += dfs(grid, nx, ny, ex, ey, empty);
}
empty++;
grid[i][j] = 0;
return x;
}
int uniquePathsIII(vector<vector<int> >& grid){
int empty = 0;
int sx, sy, ex, ey;
int n = grid.size();
int m = grid[0].size();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == 0)
empty++;
else if (grid[i][j] == 1) {
sx = i;
sy = j;
}
else if (grid[i][j] == 2) {
ex = i;
ey = j;
}
}
}
return dfs(grid, sx, sy, ex, ey, empty);
}
};
main(){
Solution ob;
vector<vector<int>> v = {{1,0,0,0},{0,0,0,0},{0,0,2,-1}};
cout << (ob.uniquePathsIII(v));
}输入值
{{1,0,0,0},{0,0,0,0},{0,0,2,-1}}输出结果
2