グリッド上のBFS
(Graph/ShortestPath/grid_bfs.py)

• View this file on GitHub
• Last update: 2022-01-22 12:11:49+09:00

概要

二次元グリッドグラフ上の単一始点最短経路問題を解くアルゴリズム。

使い方

bfs(grid: Sequence[str], si: int, sj: int, wall: str) -> List[List[int]]
グリッドグラフ grid 上での、(si, sj) を始点とした単一始点最短距離の配列を返す。グリッドグラフの大きさを h * w としたとき、計算量 $O(hw)$

Code

# from collections import deque
from standard_library.collections import deque


def grid_bfs(grid, si, sj, wall="#"):
    INF = 10 ** 18
    d = ((1, 0), (-1, 0), (0, 1), (0, -1))
    h, w = len(grid), len(grid[0])
    dist = [[INF] * w for i in range(h)]
    dist[si][sj] = 0
    que = deque([(si, sj)])
    while que:
        i, j = que.popleft()
        for di, dj in d:
            nxt_i, nxt_j = i + di, j + dj
            if not(0 <= nxt_i < h and 0 <= nxt_j < w):
                continue
            if grid[nxt_i][nxt_j] == wall:
                continue
            if dist[nxt_i][nxt_j] != INF:
                continue
            dist[nxt_i][nxt_j] = dist[i][j] + 1
            que.append((nxt_i, nxt_j))
    return dist

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page