สมมติว่ามีเมทริกซ์สองมิติ M แต่ละเซลล์มีค่าแทนสี และเซลล์ติดกัน (บน, ล่าง, ซ้าย, ขวา) ที่มีสีเดียวกันจะถูกจัดกลุ่ม การดำเนินการคือตั้งค่าทุกเซลล์ในหนึ่งกลุ่มเป็นสีหนึ่ง แล้วหาจำนวนการดำเนินการน้อยสุดเพื่อให้ทุกเซลล์มีสีเดียวกัน และเมื่อสีเปลี่ยนแล้วไม่สามารถตั้งค่าอีกครั้ง
เช่น ถ้าอินพุตเป็นเมทริกซ์ดังภาพ ผลลัพธ์จะเป็น 2
ขั้นตอนการแก้ปัญหา
- ถ้า matrix ว่าง คืนค่า 0
- กำหนดฟังก์ชัน dfs() รับ i, j, matrix, val
- n, m := ขนาดแถวและคอลัมน์
- ถ้าออกนอกขอบเขต หรือ matrix[i][j] == -1 คืนค่า
- ถ้า matrix[i][j] == val matrix[i][j] := -1 เรียก dfs 4 ทิศทาง
- มิฉะนั้น คืนค่า
- จากเมธอดหลัก
- n, m := ขนาด
- d := defaultdict(int)
- for i, j ทุกเซลล์ val := matrix[i][j] ถ้า val != -1 d[val] += 1, dfs(i, j, matrix, val)
- เรียง d ตามค่า safe := ค่าสุดท้ายของลิสต์ที่เรียงแล้ว
- res := 0 สำหรับ k, v ใน d ถ้า k != safe res += v
- คืนค่า res
ตัวอย่างโค้ด
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 - 1 or j < 0 or j > m - 1:
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)
else:
return
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))
อินพุต
matrix = [[2, 2, 2, 2],[1, 1, 1, 1],[2, 3, 2, 1]]
เอาต์พุต
2
