假设我们有一个二维网格,有4种正方形-
在正方形中,1是起点。恰好会有一个起始方块。
在正方形中2是终点。恰好会有一个结尾正方形。
在正方形中,0是空的正方形,我们可以走过去。
如果遇到障碍,我们不能走过正方形-1。
我们必须找到从开始方块到结束方块的4向步行次数,这些步行在每个非障碍方块上恰好走了一次。
所以,如果输入像-
1 | 0 | 0 | 0 |
0 | 0 | 0 | 0 |
1 | 0 | 2 | -1 |
那么输出将为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