Cho mảng 2D ký tự grid kích thước m x n. Kiểm tra có chu trình độ dài ≥ 4 không. Chu trình: đường đi bắt đầu và kết thúc cùng vị trí, chỉ đi 4 hướng, cùng ký tự, không quay lại ô đã đi.
Ví dụ: lưới như hình (ký tự 'm' tạo thành chu trình), đầu ra = True.
Giải pháp
DFS với 3 màu (WHITE=0, GRAY=1, BLACK=2) phát hiện chu trình trong đồ thị vô hướng:
- R, C := hàng, cột
- color := defaultdict(int)
- dfs(r, c, pr=-1, pc=-1):
- color[r,c] = GRAY
- Với 4 hướng (x,y):
- nr,nc = r+x, c+y
- Nếu trong lưới, cùng ký tự, không phải cha:
- Nếu WHITE: nếu dfs(nr,nc,r,c): return True
- Nếu GRAY: return True (phát hiện chu trình)
- color[r,c] = BLACK, return False
- Duyệt tất cả ô WHITE, gọi dfs, nếu True trả về True
- Trả về False
Ví dụ minh họa
Xem triển khai sau để hiểu rõ hơn:
from collections import defaultdict
di = [(0,1),(1,0),(0,-1),(-1,0)]
def solve(grid):
WHITE, GRAY, BLACK = 0, 1, 2
R, C = len(grid), len(grid[0])
color = defaultdict(int)
def dfs(r, c, pr=-1, pc=-1):
color[r,c] = GRAY
for x, y in di:
nr, nc = r+x, c+y
if (0 <= nr < R and 0 <= nc < C and grid[r][c] == grid[nr][nc] and (nr,nc) != (pr,pc)):
if color[nr,nc] == WHITE:
if dfs(nr, nc, r, c):
return True
elif color[nr,nc] == GRAY:
return True
color[r,c] = BLACK
return False
for r in range(R):
for c in range(C):
if color[r,c] == WHITE:
if dfs(r, c):
return True
return False
matrix = [["m","m","m","p"],["m","k","m","m"],["m","m","s","m"],["f","m","m","m"]]
print(solve(matrix))
Đầu vào
[["m","m","m","p"],["m","k","m","m"],["m","m","s","m"],["f","m","m","m"]]
Đầu ra
True