Cho ma trận 2D M, mỗi ô có màu. Ô cùng màu liên thông (trên/dưới/trái/phải) tạo thành nhóm. Mỗi phép toán: chọn một nhóm và đổi màu toàn bộ nhóm. Màu đã đổi không thể đổi lại. Tìm số phép tối thiểu để toàn bộ ma trận cùng màu.
Ví dụ
Đầu vào: ma trận 3x4 (xem code).
Đầu ra: 2 (đổi nhóm màu 2 thành 1, rồi nhóm màu 3 thành 1).
Thuật toán
- DFS tìm các nhóm liên thông, đếm số nhóm cho mỗi màu.
- Chọn màu có số nhóm nhiều nhất làm màu "an toàn" (không cần đổi).
- Tổng phép = tổng số nhóm của các màu khác.
Mã nguồn Python
from collections import defaultdict
class Solution:
def solve(self, matrix):
if not matrix:
return 0
def dfs(i, j, matrix, val):
n, m = len(matrix), len(matrix[0])
if i < 0 or i >= n or j < 0 or j >= m:
return
if matrix[i][j] == -1:
return
if matrix[i][j] == val:
matrix[i][j] = -1
dfs(i, j+1, matrix, val)
dfs(i+1, j, matrix, val)
dfs(i, j-1, matrix, val)
dfs(i-1, j, matrix, val)
n, m = len(matrix), len(matrix[0])
d = defaultdict(int)
for i in range(n):
for j in range(m):
val = matrix[i][j]
if val != -1:
d[val] += 1
dfs(i, j, matrix, val)
l = sorted(d, key=lambda x: d[x])
safe = l[-1]
res = 0
for k, v in d.items():
if k != safe:
res += v
return res
ob = Solution()
matrix = [
[2, 2, 2, 2],
[1, 1, 1, 1],
[2, 3, 2, 1]
]
print(ob.solve(matrix))
Đầu vào / Đầu ra
Input: matrix = [[2,2,2,2],[1,1,1,1],[2,3,2,1]]
Output: 2