Cho ma trận nhị phân, trong đó 0 đại diện cho nước, 1 đại diện cho đất. Một đảo là nhóm các ô 1 liên kết theo 4 hướng (lên, xuống, trái, phải). Ta cần tìm độ dài cầu ngắn nhất để nối hai đảo lại với nhau.
Ví dụ với ma trận:
| 0 | 0 | 1 |
| 1 | 0 | 1 |
| 1 | 0 | 0 |
Kết quả là 1, nối từ (1,0) đến (1,2).
Giải thuật (DFS + BFS)
- Dùng DFS để tìm và đánh dấu tất cả ô thuộc đảo đầu tiên (gán vào tập
seen). - Từ các ô biên của đảo đầu tiên, đẩy các ô nước liền kề vào hàng đợi BFS với khoảng cách
1. - Thực hiện BFS mở rộng ra ngoài. Khi gặp ô đất (
1) chưa thuộc đảo đầu tiên → trả vềdist - 1.
Ví dụ minh họa
import collections
class Solution:
def solve(self, mat):
row = len(mat)
col = len(mat[0])
def dfs(i, j, s):
if (i, j) in s or mat[i][j] == 0:
return
s.add((i, j))
for ni, nj in [(i-1,j), (i+1,j), (i,j-1), (i,j+1)]:
if 0 <= ni < row and 0 <= nj < col:
dfs(ni, nj, s)
seen = set()
# Tìm đảo đầu tiên
for i in range(row):
if seen: break
for j in range(col):
if mat[i][j] == 1:
dfs(i, j, seen)
break
q = collections.deque()
# Khởi tạo BFS từ biên đảo đầu tiên
for i, j in seen:
for ni, nj in [(i-1,j), (i+1,j), (i,j-1), (i,j+1)]:
if 0 <= ni < row and 0 <= nj < col and mat[ni][nj] == 0:
q.append((ni, nj, 1))
# BFS
while q:
i, j, dist = q.popleft()
if (i, j) in seen:
continue
seen.add((i, j))
if mat[i][j] == 1:
return dist - 1
for ni, nj in [(i-1,j), (i+1,j), (i,j-1), (i,j+1)]:
if 0 <= ni < row and 0 <= nj < col:
q.append((ni, nj, dist + 1))
ob = Solution()
matrix = [[0,0,1],[1,0,1],[1,0,0]]
print(ob.solve(matrix)) # Output: 1
Đầu vào / Đầu ra
Input: [[0,0,1],[1,0,1],[1,0,0]]
Output: 1