Submission #70054569

---

Source Code Expand

from collections import deque

h, w = map(int, input().split())
s = [list(input().strip()) for _ in range(h)]
for i in range(h):
  for j in range(w):
    if s[i][j] == 'T':
      t = (i, j)
init = {(i, j) for i in range(h) for j in range(w) if s[i][j] == '#'}
dirs = [(-1,0),(1,0),(0,-1),(0,1)]
visited = set([frozenset(init)])
q = deque([(init, 0)])
while q:
  cur, d = q.popleft()
  for dr, dc in dirs:
    new = set()
    dirty = False
    for r, c in cur:
      nr, nc = r + dr, c + dc
      if 0 <= nr < h and 0 <= nc < w:
        if (nr, nc) == t:
          dirty = True
          break
        new.add((nr, nc))
    if dirty:
      continue
    if not new:
      print(d + 1)
      exit()
    fs = frozenset(new)
    if fs not in visited:
      visited.add(fs)
      q.append((new, d + 1))
print(-1)

Submission Info

Judge Result