728x90
from collections import deque
for tc in range(1, int(input()) + 1):
n, m = map(int, input().split())
visited = [[-1] * m for _ in range(n)]
_map = []
q = deque()
for i in range(n):
tmp = input()
for j in range(m):
if tmp[j]=='W':
q.append((i, j))
visited[i][j] = 0
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs():
while q:
x, y = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or nx >= n or ny < 0 or ny >= m: continue
if visited[nx][ny] != -1: continue
q.append((nx, ny))
visited[nx][ny] = visited[x][y] + 1
bfs()
result = 0
for i in range(n):
for j in range(m):
result += visited[i][j]
print("#{} {}".format(tc, result))
최소 거리를 구해야하므로 BFS로 풀었다.
L에서 W까지의 최소거리를 구해야해서 W에서 시작한 최소거리를 구했다.
visited를 -1로 초기화를 했는데, 이는 W가 있는 위치는 0으로 만들어야 최소거리가 구해지기 때문이다.
'STUDY > Algorithm' 카테고리의 다른 글
[백준] 12100. 2048(Easy) (0) | 2021.03.16 |
---|---|
[SWEA] 1952 수영장 (0) | 2021.03.14 |
[SWEA] 1953 탈주범 검거 (0) | 2021.03.14 |
[SWEA] 1949 등산로 조성, 모의 SW 역량테스트, python (0) | 2021.03.11 |
[백준, SWEA] BOJ 14889 스타트와 링크, swea4012 요리사 (0) | 2021.03.10 |