64 lines
1.7 KiB
Python
64 lines
1.7 KiB
Python
from collections import deque
|
|
import sys
|
|
input = sys.stdin.readline
|
|
|
|
ans = []
|
|
|
|
def solv() :
|
|
h, w = map(int, input().split())
|
|
|
|
Map = []
|
|
Map.append("." * (w + 2))
|
|
for _ in range(h) :
|
|
Map.append("." + input().rstrip() + ".")
|
|
Map.append("." * (w + 2))
|
|
|
|
key = [False] * 26
|
|
for k in input().rstrip() :
|
|
if k != "0" :
|
|
key[ord(k) - ord("a")] = True
|
|
|
|
qu = deque()
|
|
gate = [deque() for _ in range(26)]
|
|
qu.append((0,0))
|
|
visited = [[False] * (w + 2) for _ in range(h + 2)]
|
|
res = 0
|
|
|
|
while qu :
|
|
cx, cy = qu.popleft()
|
|
|
|
for dx, dy in zip([1,-1,0,0], [0,0,1,-1]) :
|
|
nx, ny = cx + dx, cy + dy
|
|
|
|
if nx < 0 or nx >= w+2 or ny < 0 or ny >= h+2 or visited[ny][nx] or Map[ny][nx] == "*" :
|
|
continue
|
|
|
|
ch = Map[ny][nx]
|
|
|
|
if ord("A") <= ord(ch) <= ord("Z") :
|
|
if not key[ord(ch) - ord("A")] :
|
|
gate[ord(ch) - ord("A")].append((nx, ny))
|
|
else :
|
|
qu.append((nx, ny))
|
|
|
|
elif ord("a") <= ord(ch) <= ord("z") :
|
|
qu.append((nx, ny))
|
|
key[ord(ch) - ord("a")] = True
|
|
while gate[ord(ch) - ord("a")] :
|
|
qu.append(gate[ord(ch) - ord("a")].popleft())
|
|
|
|
elif ch == "$" :
|
|
res += 1
|
|
qu.append((nx, ny))
|
|
|
|
else :
|
|
qu.append((nx, ny))
|
|
|
|
visited[ny][nx] = True
|
|
|
|
ans.append(res)
|
|
|
|
for _ in range(int(input())) :
|
|
solv()
|
|
|
|
print("\n".join(map(str, ans))) |