Số mã hóa trong C ++

Giả sử chúng ta đã đưa ra một mảng 2D A, bây giờ mỗi ô là 0 (đại diện cho biển) hoặc 1 (đại diện cho đất) Ở đây, một bước di chuyển bao gồm đi bộ từ một ô đất theo hướng 4 đến một ô đất khác hoặc ra khỏi ranh giới của lưới. Chúng ta phải tìm số ô đất trong lưới mà chúng ta không thể đi ra khỏi ranh giới của lưới trong bất kỳ số lần di chuyển nào. Vì vậy, nếu lưới giống như -

Câu trả lời sẽ là 3, vì có ba câu trả lời được bao bởi số 0 và một câu trả lời là số 1 không được bao quanh.

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

• Tạo dir mảng hướng và lưu trữ [[1,0], [-1,0], [0,1], [0, -1]]

• tạo một phương thức gọi là dfs (), phương thức này sẽ lấy x, y và ma trận A

• nếu x <0 hoặc y> 0 hoặc x> số hàng của A hoặc y> số cột của A hoặc A [x, y] là 0, thì trả về

• đặt A [x, y]:=0

• cho k trong phạm vi 0 đến 3

  • nx:=dir [k, 0] + x, ny:=dir [k, 1] + y

  • dfs (nx, ny, A)

• Từ phương thức chính, hãy làm như sau

• ret:=0, n:=số hàng của A

• m:=số cột của A nếu n không phải 0, ngược lại m:=0

• cho tôi trong phạm vi từ 0 đến n - 1

  • nếu A [i, 0] =1, thì gọi dfs (i, 0, A)

  • nếu A [i, m - 1] là 1, thì gọi dfs (i, m - 1, A)

• cho tôi trong phạm vi từ 0 đến m - 1

  • nếu A [0, i] =1, thì gọi dfs (0, i, A)

  • nếu A [n - 1, i] là 1, thì gọi dfs (n - 1, i, A)

• cho tôi trong phạm vi từ 0 đến n - 1

  • cho j trong phạm vi 0 đến m - 1

    • ret:=ret + A [i, j]

• trả lại ret

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:
   void dfs(int x, int y, vector < vector <int>>& A){
      if(x < 0 || y < 0 || x >= A.size() || y >= A[0].size() ||
      A[x][y] == 0) return;
      A[x][y] = 0;
      for(int k = 0; k < 4; k++){
         int nx = dir[k][0] + x;
         int ny = dir[k][1] + y;
         dfs(nx, ny, A);
      }
   }
   int numEnclaves(vector<vector<int>>& A) {
      int ret = 0;
      int n = A.size();
      int m = n ? A[0].size() : 0;
      for(int i = 0; i < n; i++){
         if(A[i][0] == 1){
            dfs(i, 0, A);
         }
         if(A[i][m - 1] == 1){
            dfs(i, m - 1, A);
         }
      }
      for(int i = 0; i < m; i++){
         if(A[0][i] == 1){
            dfs(0, i, A);
         }
         if(A[n - 1][i] == 1){
            dfs(n - 1, i, A);
         }
      }
      for(int i = 0; i < n; i++){
         for(int j = 0; j < m; j++){
            ret += A[i][j];
         }
      }
      return ret;
   }
};
main(){
   vector<vector<int>> v1 = {{0,0,0,0},{1,0,1,0},{0,1,1,0},{0,0,0,0}};
   Solution ob;
   cout << (ob.numEnclaves(v1));
}

Đầu vào

[[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]

Đầu ra

3