จำนวนเกาะที่ปิดใน C++

สมมติว่าเรามีตาราง 2D ประกอบด้วย 0s (เป็นพื้นดิน) และ 1s (เป็นน้ำ) เกาะเป็นกลุ่มสูงสุด 4 ทิศทางที่เชื่อมต่อกันเป็น 0 วินาที เกาะปิดคือเกาะที่ล้อมรอบด้วย 1s โดยสิ้นเชิง เราต้องหาจำนวนเกาะปิด ดังนั้นถ้าเส้นกริดเป็นแบบ

ดังนั้นผลลัพธ์จะเป็น 2 มีเกาะสองเกาะที่ล้อมรอบด้วยน้ำอย่างสมบูรณ์

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

• กำหนดแฟล็กตัวแปร

• กำหนดวิธีการที่เรียกว่า dfs ซึ่งจะใช้กริด i, j, n และ m

• หาก i และ j ไม่อยู่ในช่วงของกริด ให้ตั้งค่าแฟล็ก :=false และส่งคืน

• ถ้า g[i,j] =1 หรือ g[i, j] =-1 ให้ส่งคืน

• ถ้า g[i, j] =0 แล้ว g[i, j] =-1

• โทร dfs(g, i + 1, j, n, m), dfs(g, i, j+1, n, m), dfs(g, i - 1, j, n, m), dfs(g, ผม, j-1, n, ม.)

• วิธีการหลักจะเป็นเช่น -

• สร้างเมทริกซ์ dp ของคำสั่ง n x m และเติมด้วย -1

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

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

    • ถ้า g[i, j] =0 แล้ว

      • ธง :=จริง

      • dfs(g, i, j, n, m)

      • ธง :=จริง

      • ans :=ans + ธง

• กลับมาอีกครั้ง

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

ตัวอย่าง

#include ใช้เนมสเปซ std;class Solution { สาธารณะ:vector > dp; ธงบูล; โมฆะ dfs(เวกเตอร์>&g, int i, int j, int n, int m){ if(i>=n || j>=m || i<0 || j<0){ ธง =เท็จ; กลับ; } if(g[i][j] ==1 || g[i][j] ==-1)return; ถ้า(g[i][j] ==0)g[i][j] =-1; dfs(g, i+1, j, n, m); dfs(g, i, j+1, n, m); dfs(g, i-1, j, n, m); dfs(g,i, j-1, n, m); } int closedIsland(vector>&g) { int ans =0; int n =g.size(); int m =g[0].size(); dp =เวกเตอร์ <เวกเตอร์ > (n, เวกเตอร์  (m, -1)); for(int i =0; i > v ={{1,1,1,1,1,1,1,0},{1,0,0,0,0,1,1, 0},{1,0,1,0,1,1,1,1,0},{1,0,0,0,0,1,0 ,1},{1,1,1,1,1, 1,1,0}}; โซลูชัน ob; ศาล <<(ob.closedIsland(v));}

อินพุต

ผลลัพธ์

2