크기가 m x n인 그리드라고 하는 하나의 2D 문자 배열이 있다고 가정합니다. 내부에서 사이클을 감지할 수 있는지 여부를 확인해야 합니다. 여기서 사이클은 동일한 위치에서 시작하고 끝나는 그리드에서 길이가 4 이상인 경로입니다. 현재 셀의 값이 같으면 4방향(상,하,좌,우)으로 이동할 수 있으며, 일부 셀을 다시 방문할 수 없습니다.
따라서 입력이 다음과 같으면
| m | m | m | p |
| m | k | m | m |
| m | m | s | m |
| f | t | m | m |
녹색 셀이 주기를 형성하고 있기 때문에 출력은 True가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
흰색 :=0, 회색 :=1, 검정색 :=2
-
R :=그리드의 행 수
-
C :=그리드의 열 개수
-
color :=기본값이 0인 빈 지도
-
dfs() 함수를 정의합니다. r, c, pr:=-1,pc:=-1
이 필요합니다. -
색상[r,c] :=회색
-
di의 각 쌍(x,y)에 대해 수행
-
(nr,nc) :=(r+x,c+y)
-
0 <=nr
-
color[nr,nc]가 WHITE와 같으면
-
dfs(nr,nc,r,c)가 참이면
-
참을 반환
-
-
그렇지 않으면 color[nr,nc]가 GRAY와 같을 때
-
참을 반환
-
-
-
색상[r,c] :=검정색
-
거짓을 반환
-
기본 방법에서 다음을 수행하십시오.
-
0 ~ R - 1 범위의 r에 대해
-
범위 0에서 C - 1의 c에 대해 수행
-
color[r,c]가 WHITE와 같으면
-
dfs(r,c)가 참이면
-
참을 반환
-
-
-
-
-
-
-
거짓을 반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다.
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))
입력
7, [5,1,4,3]
출력
True