จำนวนวงล้อมใน C++

สมมติว่าเราได้ให้อาร์เรย์ 2 มิติ A ตอนนี้แต่ละเซลล์เป็น 0 (แสดงถึงทะเล) หรือ 1 (แสดงถึงแผ่นดิน) ในที่นี้ การเคลื่อนไหวประกอบด้วยการเดินจากสี่เหลี่ยมผืนดินหนึ่ง 4 ทิศทางไปยังอีกตารางหนึ่ง หรือนอกขอบเขตของตาราง เราต้องหาจำนวนช่องสี่เหลี่ยมในตารางที่เราไม่สามารถเดินออกจากขอบเขตของตารางในการเคลื่อนไหวจำนวนเท่าใดก็ได้ ดังนั้นหากกริดเป็นเหมือน −

คำตอบจะเป็น 3 เนื่องจากมีสามตัวที่เติมด้วย 0 และตัวที่ 1 ไม่ได้ปิดล้อม

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• สร้าง dir อาร์เรย์ทิศทาง และเก็บ [[1,0], [-1,0], [0,1], [0,-1]]

• สร้างเมธอดที่เรียกว่า dfs() ซึ่งจะใช้ x, y และเมทริกซ์ A

• ถ้า x <0 หรือ y> 0 หรือ x> จำนวนแถวของ A หรือ y> จำนวนคอลัมน์ของ A หรือ A[x, y] เป็น 0 ให้ส่งคืน

• ตั้งค่า A[x, y] :=0

• สำหรับ k ในช่วง 0 ถึง 3

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

  • dfs(nx, ny, A)

• จากวิธีหลักให้ทำดังนี้

• ret :=0, n :=จำนวนแถวของ A

• m :=จำนวนคอลัมน์ของ A ถ้า n ไม่ใช่ 0 มิฉะนั้น m :=0

• สำหรับฉันอยู่ในช่วง 0 ถึง n – 1

  • ถ้า A[i, 0] =1 ให้เรียก dfs(i, 0, A)

  • ถ้า A[i, m – 1] เป็น 1 ให้เรียก dfs(i, m – 1, A)

• สำหรับฉันในช่วง 0 ถึง m – 1

  • ถ้า A[0, i] =1 ให้เรียก dfs(0, i, A)

  • ถ้า A[n – 1, i] คือ 1 ให้เรียก dfs(n – 1, i, A)

• สำหรับฉันอยู่ในช่วง 0 ถึง n – 1

  • สำหรับ j ในช่วง 0 ถึง m – 1

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

• รีเทิร์น

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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

อินพุต

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

ผลลัพธ์

3