Source code for titan_pylib.graph.grid_bfs

 1from collections import deque
 2
 3

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