โปรแกรมหาพื้นที่เกาะที่ใหญ่ที่สุดในเมทริกซ์ใน Python

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

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

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

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

• กำหนดฟังก์ชัน dfs() นี่จะใช้เมทริกซ์, r, c
• รวม :=รวม + 1
• เมทริกซ์[r, c] :=0
• ถ้า r - 1>=0 และเมทริกซ์[r - 1, c] เท่ากับ 1 แล้ว
  • dfs(เมทริกซ์, r - 1, c)
• ถ้า c - 1>=0 และเมทริกซ์[r, c - 1] เท่ากับ 1 แล้ว
  • dfs(เมทริกซ์, r, c - 1)
• ถ้า r + 1
• dfs(เมทริกซ์, r + 1, c)

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

ตัวอย่าง

class Solution:
   def solve(self, matrix):
      self.r_len = len(matrix)
      self.c_len = len(matrix[0])
      max_island = 0
      for r in range(self.r_len):
         for c in range(self.c_len):
            if matrix[r][c] == 1:
               self.total = 0
               self.dfs(matrix, r, c)
               max_island = max(max_island, self.total)
      return max_island
   def dfs(self, matrix, r, c):
      self.total += 1
      matrix[r][c] = 0
      if r - 1 >= 0 and matrix[r - 1][c] == 1:
         self.dfs(matrix, r - 1, c)
      if c - 1 >= 0 and matrix[r][c - 1] == 1:
         self.dfs(matrix, r, c - 1)
      if r + 1 < self.r_len and matrix[r + 1][c] == 1:
         self.dfs(matrix, r + 1, c)
      if c + 1 < self.c_len and matrix[r][c + 1] == 1:
         self.dfs(matrix, r, c + 1)
ob = Solution()
matrix = [ [0, 0, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0, 0], [0, 1, 1, 1, 1, 0, 0], [0, 0, 1, 1, 0, 0, 0], [0, 0, 0, 0, 0, 1, 1], [0, 0, 0, 0, 0, 1, 0] ]
print(ob.solve(matrix))

อินพุต

matrix = [
[0, 0, 1, 1, 1, 1, 1],
[0, 0, 0, 0, 0, 0, 0],
[0, 1, 1, 1, 1, 0, 0],
[0, 0, 1, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 1, 1],
[0, 0, 0, 0, 0, 1, 0] ]

ผลลัพธ์

6