Các đường dẫn duy nhất III trong C ++

Giả sử chúng ta có một lưới 2 chiều, có 4 loại hình vuông -

Trong hình vuông, 1 là điểm bắt đầu. Sẽ có đúng một ô vuông bắt đầu.
Trong hình vuông 2 là điểm kết thúc. Sẽ có đúng một ô vuông kết thúc.
Trong ô vuông 0 là ô trống và chúng ta có thể đi qua.
Trong hình vuông -1 nếu có chướng ngại vật mà chúng ta không thể vượt qua.

Chúng ta phải tìm số lần đi bộ theo 4 hướng từ hình vuông bắt đầu đến hình vuông kết thúc, đi qua mỗi hình vuông không chướng ngại vật chính xác một lần.

Vì vậy, nếu đầu vào giống như -

1	0	0
0	0	0
1	2	-1

thì đầu ra sẽ là 2, vì chúng ta có hai đường dẫn sau:(0,0), (0,1), (0,2), (0,3), (1,3), (1,2), (1,1), (1,0), (2,0), (2,1), (2,2) và (0,0), (1,0), (2,0), (2 , 1), (1,1), (0,1), (0,2), (0,3), (1,3), (1,2), (2,2).

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Xác định một hàm dfs (), hàm này sẽ lấy một lưới mảng 2D, i, j, ex, ey, trống,
nếu i, j không thuộc phạm vi lưới hoặc lưới [i, j] giống -1, thì -
- trả về 0
nếu lưới [i, j] giống 2 thì
- trả về true khi giá trị trống là -1
x:=0
(giảm trống đi 1)
lưới [i, j]:=-1
để khởi tạo k:=0, khi k <4, cập nhật (tăng k lên 1), thực hiện -
- nx:=i + dir [k, 0]
- ny:=j + dir [k, 1]
- x:=x + dfs (lưới, nx, ny, ex, ey, trống)
(tăng trống lên 1)
lưới [i, j]:=0
trả lại x
Từ phương pháp làm như sau -
trống:=0
n:=Số hàng, m:=Số cột
để khởi tạo i:=0, khi i
- để khởi tạo j:=0, khi j
  - nếu lưới [i, j] giống 0 thì
    - (tăng trống lên 1)
  - ngược lại khi lưới [i, j] giống 1 thì -
    - sx:=i, sy:=j
  - ngược lại khi lưới [i, j] giống như 2, thì -
    - ví dụ:=i, ey:=j
trả về dfs (lưới, sx, sy, ex, ey, trống)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

{{1,0,0,0},{0,0,0,0},{0,0,2,-1}}

Các đường dẫn duy nhất III trong C ++

Ví dụ

Đầu vào

Đầu ra