Bài toán: Cho ma trận vuông mat kích thước N×N chứa chỉ 0 và 1. Phần tử 1 = đã kết nối, 0 = chưa kết nối. Tìm độ dài đường đi lớn nhất có thể đạt được bằng cách chuyển **tối đa một** ô 0 thành 1.
Đường đi: chuỗi các ô 1 liền kề nhau (4 hướng: lên, xuống, trái, phải).
Ví dụ
Input: mat = [[1, 0],
[0, 1]]
Output: 3
Giải thích: Chuyển (0,1) hoặc (1,0) thành 1 -> đường đi 3 ô.
Giải pháp: DFS + Nhóm thành phần liên thông
Ý tưởng: Gán nhãn (index) cho mỗi thành phần liên thông của 1, lưu kích thước. Với mỗi ô 0, xem nó kết nối được những thành phần nào -> tổng kích thước + 1.
def find_max_path_binary_matrix(mat):
"""
Tìm đường đi dài nhất trong ma trận nhị phân sau khi flip tối đa 1 ô 0->1.
Args:
mat: List[List[int]] - ma trận N×N chỉ chứa 0 và 1
Returns:
int - độ dài đường đi lớn nhất
"""
N = len(mat)
if N == 0:
return 0
# 1. Tìm các thành phần liên thông của 1, gán nhãn (index >= 2)
# Dùng index >= 2 để phân biệt với 0 và 1 gốc
component_size = {} # index -> size
index = 2
def dfs(r, c, idx):
"""DFS gán nhãn và trả về kích thước component."""
if r < 0 or r >= N or c < 0 or c >= N or mat[r][c] != 1:
return 0
mat[r][c] = idx
size = 1
for dr, dc in [(-1,0), (1,0), (0,-1), (0,1)]:
size += dfs(r+dr, c+dc, idx)
return size
for i in range(N):
for j in range(N):
if mat[i][j] == 1:
component_size[index] = dfs(i, j, index)
index += 1
# 2. Kích thước lớn nhất hiện tại (chưa flip 0 nào)
max_path = max(component_size.values()) if component_size else 0
# 3. Thử flip mỗi ô 0
for i in range(N):
for j in range(N):
if mat[i][j] == 0:
# Tìm các component lân cận duy nhất
neighbor_components = set()
for di, dj in [(-1,0), (1,0), (0,-1), (0,1)]:
ni, nj = i + di, j + dj
if 0 <= ni < N and 0 <= nj < N and mat[ni][nj] > 1:
neighbor_components.add(mat[ni][nj])
# Tổng kích thước các component lân cận + 1 (ô hiện tại)
combined_size = 1 + sum(component_size[idx] for idx in neighbor_components)
max_path = max(max_path, combined_size)
return max_path
# Test
mat1 = [[1, 0], [0, 1]]
print(f"Test 1: {find_max_path_binary_matrix([row[:] for row in mat1])}") # 3
mat2 = [[1, 1, 0], [1, 0, 1], [0, 1, 1]]
print(f"Test 2: {find_max_path_binary_matrix([row[:] for row in mat2])}") # 7
mat3 = [[0, 0], [0, 0]]
print(f"Test 3 (all 0): {find_max_path_binary_matrix([row[:] for row in mat3])}") # 1
mat4 = [[1, 1], [1, 1]]
print(f"Test 4 (all 1): {find_max_path_binary_matrix([row[:] for row in mat4])}") # 4
Kết quả
Test 1: 3 Test 2: 7 Test 3 (all 0): 1 Test 4 (all 1): 4
Giải thích thuật toán
- DFS gán nhãn: Duyệt ma trận, mỗi component 1 được gán index duy nhất (2, 3, 4...), lưu kích thước vào dict.
- Tính max ban đầu: Component lớn nhất hiện tại.
- Thử flip mỗi 0: Với mỗi ô 0, xem 4 hàng xóm. Thu thập các index component duy nhất. Tổng size = 1 + sum(size của các component lân cận).
- Trả về max của tất cả khả năng.
Độ phức tạp
- Thời gian:
O(N²)- mỗi ô được thăm O(1) lần. - Không gian:
O(N²)- lưu ma trận và dict component (tối đa N²/2 component).
Lưu ý
Hàm sửa đổi ma trận gốc (gán nhãn). Truyền [row[:] for row in mat] để copy nếu cần giữ nguyên.