คำอธิบายโจทย์
เมทริกซ์ไบนารี 1=ที่ดิน 0=น้ำ เกาะ = กลุ่ม 1 ติดกัน (4 ทิศทาง) ลบเกาะที่ถูนน้ำล้อมรอบสมบูรณ์ (ไม่ติดขอบ) โดยเปลี่ยนเป็น 0
ตัวอย่าง
Input: เกาะกลางติดขอบไม่ถูกลบ, เกาะกลางถูมน้ำล้อม → ถูกลบ
Output: เหลือแค่เกาะมุม
วิธีแก้ปัญหา
BFS/DFS จากขอบ (Boundary-connected Components):
- เริ่ม BFS จากเซลล์ 1 ที่อยู่บนขอบ (แถว 0, R-1 หรือคอลัมน์ 0, C-1)
- Mark ทุกเซลล์ที่ reachable จากขอบ → เกิด matrix B
- เซลล์ 1 ที่ไม่ถูก mark = เกาะถูกล้อมรอบ → กลายเป็น 0
- คืนค่า B (มีแค่เกาะติดขอบเหลือ)
โค้ด Python
from collections import deque
class Solution:
def solve(self, A):
row = len(A)
col = len(A[0])
B = [[0 for _ in range(col)] for _ in range(row)]
seen = set()
def nei(i, j):
if i + 1 < row and A[i + 1][j]:
yield (i + 1, j)
if j + 1 < col and A[i][j + 1]:
yield (i, j + 1)
if i - 1 >= 0 and A[i - 1][j]:
yield (i - 1, j)
if j - 1 >= 0 and A[i][j - 1]:
yield (i, j - 1)
for i in range(row):
for j in range(col):
if i not in (0, row - 1) and j not in (0, col - 1):
continue
if (i, j) in seen:
continue
if A[i][j] == 0:
continue
d = deque([(i, j)])
seen.add((i, j))
while d:
x, y = d.popleft()
B[x][y] = 1
for x2, y2 in nei(x, y):
if (x2, y2) not in seen:
d.append((x2, y2))
seen.add((x2, y2))
return B
ob = Solution()
matrix = [
[1, 0, 0, 0],
[0, 1, 1, 0],
[0, 1, 1, 0],
[0, 1, 1, 0],
[0, 0, 0, 1],
]
print(ob.solve(matrix))
อินพุต
[[1,0,0,0],[0,1,1,0],[0,1,1,0],[0,1,1,0],[0,0,0,1]]
เอาต์พุต
[[1,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,1]]
