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

เมทริกซ์ไบนารี 1=บก 0=น้ำ เกาะคือกลุ่ม 1 ที่ต่อกัน หาเกาะที่ล้อมรอบน้ำหมด (ไม่สัมผัสขอบเมทริกซ์)

เช่น เมทริกซ์ 6x5 มี 3 เกาะ แต่ 2 เกาะถูกล้อมรอบน้ำ ให้ผลลัพธ์ 2

ขั้นตอนการแก้ปัญหา

• DFS จากทุกเซลล์ที่เป็น 1
• ถ้า DFS พบขอบเมทริกซ์ คืน False (ไม่ถูกล้อมรอบ)
• ถ้า DFS จบโดยไม่พบขอบ คืน True (ถูกล้อมรอบ)
• นับจำนวนครั้งที่ DFS คืน True

ตัวอย่างโค้ด

class Solution:
    def solve(self, matrix):
        def dfs(i,j):
            if i<0 or j<0 or i>=R or j>=C: return False
            if matrix[i][j]==0: return 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)
            return a and b and c and 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 ans

ob = 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))

อินพุต

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]]

เอาต์พุต

2