C++의 고유 경로 III

1개의 2차원 그리드가 있다고 가정하면 4가지 유형의 정사각형이 있습니다. −

정사각형에서 1은 시작점입니다. 정확히 하나의 시작 사각형이 있을 것입니다.
정사각형에서 2는 끝점입니다. 정확히 하나의 끝 사각형이 있습니다.
사각형에서 0은 빈 사각형이고 우리는 건너갈 수 있습니다.
우리가 걸을 수 없는 장애물의 경우 사각형에서 -1입니다.

시작 사각형에서 끝 사각형까지의 4방향 보행 횟수를 찾아야 합니다. 이 보행은 모든 장애물이 없는 사각형을 정확히 한 번만 지나야 합니다.

따라서 입력이 다음과 같으면 -

1	0	0
0	0	0
1	2	-1

(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씩 증가)
그리드[i, j] :=0
x를 반환
방법에서 다음을 수행하십시오 -
비어 있음 :=0
n :=행 개수, m :=열 개수
initialize i :=0의 경우, i
- j 초기화의 경우:=0, j
  - grid[i, j]가 0과 같으면
    - (공백을 1씩 증가)
  - 그렇지 않으면 grid[i, j]가 1과 같을 때 -
    - sx :=i, sy :=j
  - 그렇지 않으면 grid[i, j]가 2와 같을 때 -
    - 예 :=나는, ey :=j
반환 dfs(그리드, 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}}

C++의 고유 경로 III

예시

입력

출력