C ++中的独特路径III

假设我们有一个二维网格,有4种正方形-

  • 在正方形中,1是起点。恰好会有一个起始方块。

  • 在正方形中2是终点。恰好会有一个结尾正方形。

  • 在正方形中,0是空的正方形,我们可以走过去。

  • 如果遇到障碍,我们不能走过正方形-1。

我们必须找到从开始方块到结束方块的4向步行次数,这些步行在每个非障碍方块上恰好走了一次。

所以,如果输入像-

1000
0000
102-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