Cho ma trận nhị phân: 1 (đất), 0 (nước). Đảo là nhóm 1 liên thông 4 hướng. Xóa (biến thành 0) tất cả đảo bị bao quanh hoàn toàn bởi nước (không chạm biên ma trận).
Ví dụ ma trận 5x4: đảo giữa bị xóa, đảo góc trên trái và góc dưới phải giữ nguyên.
Giải pháp
BFS/DFS từ các ô đất trên BIÊN ma trận, đánh dấu tất cả đảo kết nối với biên (không bị xóa). Các đảo còn lại là đảo bị bao quanh, biến thành 0.
- Khởi tạo ma trận kết quả B toàn 0
- Duyệt các ô trên biên (hàng 0, hàng cuối, cột 0, cột cuối)
- Nếu là đất và chưa thăm: BFS đánh dấu seen, đặt B[x][y] = 1
- Trả về B
Ví dụ minh họa
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)])
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))
Đầu vào
[[1,0,0,0],[0,1,1,0],[0,1,1,0],[0,1,1,0],[0,0,0,1]]
Đầu ra
[[1,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,1]]