'O'는 열린 공간, 'G'는 경비원, 'W'는 은행의 벽을 나타내며, 한 경비원으로부터의 최단 거리와 관련하여 매트릭스의 모든 O를 교체해야 합니다. 어떤 벽도 통과할 수 없습니다. 출력 매트릭스에서 가드는 0으로 대체되고 벽은 -1로 대체됩니다.
따라서 입력이 다음과 같으면
| O | O | O | O | G |
| O | O | O | W | O |
| O | W | O | O | O |
| G | W | W | W | O |
| O | O | O | O | G |
그러면 출력은
| 3 | 3 | 2 | 1 | 0 |
| 2 | 3 | 3 | -1 | 1 |
| 1 | -1 | 4 | 3 | 2 |
| 0 | -1 | -1 | -1 | 1 |
| 1 | 2 | 2 | 1 | 0 |
이 문제를 해결하기 위해 다음 단계를 따릅니다.
-
남 :=5
-
N :=5
-
디렉토리 행 :=[-1, 0, 1, 0]
-
dir_col :=[0, 1, 0, -1]
-
is_ok() 함수를 정의합니다. 이것은 i, j가 걸릴 것입니다
-
(i 범위 0 및 M) 또는 (j 범위 0 및 j N)인 경우
-
거짓을 반환
-
-
참을 반환
-
isSafe() 함수를 정의합니다. 이것은 i, j, 행렬, 결과를 취합니다.
-
행렬[i, j]가 'O'가 아니거나 결과[i, j]가 -1이 아니면
-
거짓을 반환
-
-
참을 반환
-
compute_dist() 함수를 정의합니다. 이것은 행렬을 취합니다.
-
result :=M x N 차수의 행렬을 만들고 -1로 채움
-
이중 종료 대기열 정의 q
-
범위 0에서 M에 있는 i에 대해 수행
-
0에서 N 사이의 j에 대해 수행
-
결과[i, j] :=-1
-
행렬[i, j]이 'G'와 같으면
-
위치 :=[i, j, 0]
-
q 왼쪽에 pos 삽입
-
결과[i, j] :=0
-
-
-
-
q> 0의 크기가 0이 아닌 동안 수행
-
curr :=q에서 마지막 요소 삭제
-
x, y, dist :=curr[0], curr[1], curr[2]
-
범위 0에서 3까지의 i에 대해 수행
-
is_ok(x + dir_row[i], y + dir_col[i])가 0이 아니고 isSafe(x + dir_row[i], y + dir_col[i], matrix, result)가 0이 아니면
-
결과[x + dir_row[i], y + dir_col[i]] :=dist + 1
-
위치 :=[x + dir_row[i], y + dir_col[i], dist + 1]
-
q 왼쪽에 pos 삽입
-
-
-
-
범위 0에서 M에 있는 i에 대해 수행
-
0에서 N 사이의 j에 대해 수행
-
결과 표시[i,j]
-
-
다음 줄로 이동
-
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
from collections import deque as queue M = 5 N = 5 dir_row = [-1, 0, 1, 0] dir_col = [0, 1, 0, -1] def is_ok(i, j): if ((i < 0 or i > M - 1) or (j < 0 or j > N - 1)): return False return True def isSafe(i, j,matrix, result): if (matrix[i][j] != 'O' or result[i][j] != -1): return False return True def calculate_dist(matrix): result = [[ -1 for i in range(N)]for i in range(M)] q = queue() for i in range(M): for j in range(N): result[i][j] = -1 if (matrix[i][j] == 'G'): pos = [i, j, 0] q.appendleft(pos) result[i][j] = 0 while (len(q) > 0): curr = q.pop() x, y, dist = curr[0], curr[1], curr[2] for i in range(4): if is_ok(x + dir_row[i], y + dir_col[i]) and isSafe(x + dir_row[i], y + dir_col[i], matrix, result) : result[x + dir_row[i]][y + dir_col[i]] = dist + 1 pos = [x + dir_row[i], y + dir_col[i], dist + 1] q.appendleft(pos) for i in range(M): for j in range(N): if result[i][j] > 0: print(result[i][j], end=" ") else: print(result[i][j],end=" ") print() matrix = [['O', 'O', 'O', 'O', 'G'], ['O', 'O', 'O', 'W', 'O'], ['O', 'W', 'O', 'O', 'O'], ['G', 'W', 'W', 'W', 'O'], ['O', 'O', 'O', 'O', 'G']] calculate_dist(matrix)
입력
[['O', 'O', 'O', 'O', 'G'], ['O', 'O', 'O', 'W', 'O'], ['O', 'W', 'O', 'O', 'O'], ['G', 'W', 'W', 'W', 'O'], ['O', 'O', 'O', 'O', 'G']]
출력
3 3 2 1 0 2 3 3 -1 1 1 -1 4 3 2 0 -1 -1 -1 1 1 2 2 1 0