1# from titan_pylib.graph.grid_bfs import grid_bfs
2from collections import deque
3
4
5def grid_bfs(field, sx, sy, tx, ty, ng="#"):
6 dx = [0, 1, 0, -1]
7 dy = [1, 0, -1, 0]
8 # ↓ → ↑ ←
9 n = len(field)
10 m = len(field[0])
11 dist = [[-1] * m for _ in range(n)]
12 dist[sy][sx] = 0
13 todo = deque([(sy, sx)])
14 while todo:
15 vy, vx = todo.popleft()
16 for d in range(len(dx)):
17 ny, nx = vy + dy[d], vx + dx[d]
18 if 0 <= ny < n and 0 <= nx < m:
19 if field[ny][nx] == ng or dist[ny][nx] != -1:
20 continue
21 dist[ny][nx] = dist[vy][vx] + 1
22 if ny == ty and nx == tx:
23 break
24 todo.append((ny, nx))
25 else:
26 continue
27 break
28 # return dist
29
30 direct = ("U", "L", "D", "R")
31 fukugen = []
32 di = dist[ty][tx]
33 gy, gx = ty, tx
34 while di:
35 for d in range(len(dx)):
36 ny, nx = gy + dy[d], gx + dx[d]
37 if 0 <= ny < n and 0 <= nx < m:
38 if dist[ny][nx] == di - 1:
39 di -= 1
40 fukugen.append(direct[d])
41 if ny == sy and nx == sx:
42 break
43 gy, gx = ny, nx
44 break
45 return fukugen[::-1]