โปรแกรมนับจำนวนเกาะที่ล้อมรอบในเมทริกซ์ใน python

สมมติว่าเรามีเมทริกซ์ไบนารี โดยที่ 1 หมายถึงดิน และ 0 หมายถึงน้ำ อย่างที่เราทราบกันดีว่าเกาะคือกลุ่มของ 1s ที่รวมกันเป็นกลุ่มซึ่งมีปริมณฑลล้อมรอบด้วยน้ำ เราต้องหาจำนวนเกาะที่ล้อมรอบอย่างสมบูรณ์

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

จากนั้นผลลัพธ์จะเป็น 2 เนื่องจากมีสามเกาะ แต่สองเกาะถูกล้อมรอบอย่างสมบูรณ์

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

• กำหนดฟังก์ชัน dfs() นี่จะใช้เวลา i, j
• ถ้า i และ j ไม่อยู่ในช่วงของเมทริกซ์ แล้ว
  • คืนค่าเท็จ
• ถ้าเมทริกซ์[i, j] เท่ากับ 0 แล้ว
  • คืนค่า True
• เมทริกซ์[i, j] :=0
• a :=dfs(i + 1, j)
• b :=dfs(i - 1, j)
• c :=dfs(i, j + 1)
• d :=dfs(i, j - 1)
• คืนค่า a และ b และ c และ d
• จากวิธีหลัก ให้ทำดังนี้:
• R :=จำนวนแถวของเมทริกซ์, C :=จำนวนคอลัมน์ของเมทริกซ์
• ตอบ :=0
• สำหรับผมในช่วง 0 ถึง R ให้ทำ
  • สำหรับ j ในช่วง 0 ถึง C ให้ทำ
    • ถ้า matrix[i, j] เหมือนกับ 1 แล้ว
      • ถ้า dfs(i, j) เป็นจริง ดังนั้น
        • อัน :=ans + 1
• คืนสินค้า

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

ตัวอย่าง

คลาสโซลูชัน:def แก้(ตัวเอง, เมทริกซ์):def dfs(i, j):if i <0 หรือ j <0 หรือ i>=R หรือ j>=C:คืนค่า False if matrix[i][j ] ==0:คืนค่า True matrix[i][j] =0 a =dfs(i + 1, j) b =dfs(i - 1, j) c =dfs(i, j + 1) d =dfs( i, j - 1) คืนค่า a และ b และ c และ d R, C =len(matrix), len(matrix[0]) ans =0 for i in range(R):for j in range(C):if matrix[i][j] ==1:if dfs(i, j):ans +=1 return ansob =Solution()matrix =[ [1, 0, 0, 0, 0], [0, 0, 0 , 1, 0], [0, 1, 0, 0, 0], [0, 1, 0, 0, 0], [0, 1, 1, 1, 0], [0, 0, 0, 0 , 0]]print(ob.solve(matrix))

อินพุต

ผลลัพธ์

2