from collections import deque
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
t = int(input())
for _ in range(t):
h, w = map(int, input().split())
tmp_g = [list(input()) for _ in range(h)]
keys = list(input())
ans = 0
g = [['.'] * w for _ in range(h)]
for i in range(h):
g[i] = ['.'] + tmp_g[i] + ['.']
g = [['.'] * (w+2)] + g + [['.'] * (w+2)]
def findkey(sx, sy):
check = [[-1] * (w+2) for _ in range(h+2)]
q = deque()
q.append((sx, sy))
check[sx][sy] = 0
cnt = 0
while q:
x, y = q.popleft()
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if nx < 0 or ny < 0 or nx >= h+2 or ny >= w+2:
continue
if g[nx][ny] == '*':
continue
if check[nx][ny] == -1:
if g[nx][ny].islower():
q.append((nx, ny))
check[nx][ny] = check[x][y] + 1
if g[nx][ny] not in keys:
keys.append(g[nx][ny])
cnt += 1
elif g[nx][ny].isupper():
if g[nx][ny].lower() in keys:
q.append((nx, ny))
check[nx][ny] = check[x][y] + 1
else:
q.append((nx, ny))
check[nx][ny] = check[x][y] + 1
return cnt
def bfs(sx, sy):
global ans
check = [[-1] * (w+2) for _ in range(h+2)]
q = deque()
q.append((sx, sy))
check[sx][sy] = 0
while q:
x, y = q.popleft()
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if nx < 0 or ny < 0 or nx >= h+2 or ny >= w+2:
continue
if g[nx][ny] == '*':
continue
if check[nx][ny] == -1:
if g[nx][ny] == '.' or g[nx][ny].islower():
q.append((nx, ny))
check[nx][ny] = check[x][y] + 1
elif g[nx][ny] == '$':
q.append((nx, ny))
check[nx][ny] = check[x][y] + 1
g[nx][ny] = '.'
ans += 1
else:
if g[nx][ny].lower() in keys:
q.append((nx, ny))
check[nx][ny] = check[x][y] + 1
while True:
cnt = findkey(0, 0)
if cnt == 0:
break
bfs(0, 0)
print(ans)
처음에는 check배열을 여러 차원으로 만들거나 정보를 여러개 저장할 생각으로 한번에 bfs를 돌려서 찾겠다고 생각했는데 쉽지 않았음
- bfs로 찾을 수 있는 열쇠를 모두 찾는다
- 열쇠를 찾은 후 문서를 모두 찾는다
빈칸으로 테두리 한번 패딩해줌 (들락날락할 수 있도록) -> 계속 bfs를 해주면서 key를 더이상 찾을 수 없을 때까지 key를 모두 찾아줌 -> bfs로 문서를 찾아줌