จำนวนหมู่เกาะที่แตกต่างใน C++

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

เกาะจะถือว่าเหมือนกันกับอีกเกาะหนึ่งเมื่อสามารถแปลเกาะหนึ่ง (และไม่หมุนหรือสะท้อนกลับ) ให้เท่ากันอีกเกาะหนึ่ง

ดังนั้นหากอินพุตเป็นแบบ

แล้วผลลัพธ์จะเป็น 3

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

• กำหนดฟังก์ชัน dfs() ซึ่งจะใช้เวลา x, y, grid, temp, c,

• ถ้า x และ y ไม่อยู่ในแถวและคอลัมน์ของกริด และกริด[x,y] จะเป็น 0 ดังนั้น −

  • กลับ

• กริด[x, y] :=0

• temp :=temp concatenate c

• dfs(x + 1, y, grid, temp, 'r')

• dfs(x - 1, y, grid, temp, 'l')

• dfs(x, y + 1, กริด, อุณหภูมิ, 'd')

• dfs(x, y - 1, grid, temp, 'u')

• temp :=temp concatenate 'b'

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• ยกเลิก :=0

• กำหนดการเยี่ยมชมหนึ่งชุด

• สำหรับการเริ่มต้น i :=0 เมื่อ i <จำนวนแถวของกริด ให้อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

  • สำหรับการเริ่มต้น j :=0 เมื่อ j

    • ถ้า grid[i, j] ไม่ใช่ศูนย์ ดังนั้น −

      • aux :=สตริงว่าง

      • dfs(i, j, grid, aux, 's')

      • ถ้า aux ไม่ได้เข้าใช้งาน −

        • (เพิ่มการถอยกลับโดย 1)

        • ใส่ aux เข้าไป

• รีเทิร์น

ตัวอย่าง

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

#include ใช้เนมสเปซ std;int dir[4][2] ={{1, 0}, {-1, 0}, {0, -1}, {0, 1 }};คลาสโซลูชัน {สาธารณะ:void dfs(int x, int y, vector >&grid, string&temp, char c){ if (x <0 || y <0 || x>=grid .size() || y>=grid[0].size() || !grid[x][y]) กลับ; ตาราง[x][y] =0; อุณหภูมิ +=c; dfs(x + 1, y, กริด, อุณหภูมิ, 'r'); dfs(x - 1, y, กริด, อุณหภูมิ, 'l'); dfs(x, y + 1, กริด, อุณหภูมิ, 'd'); dfs(x, y - 1, กริด, อุณหภูมิ, 'u'); อุณหภูมิ +='b'; } int numDistinctIslands (เวกเตอร์<เวกเตอร์>&ตาราง) { int ret =0; set เยี่ยมชม; สำหรับ (int i =0; i > v ={{1,1,0,1,1},{1,0,0,0,0},{0,0,0,0,1},{1,1 ,0,1,1}}; cout<<(ob.numDistinctIslands(v));}

อินพุต

ผลลัพธ์

3