Search/BreadthFirstSearch_grid.py

View this file on GitHub
Last update: 1970-01-01 00:00:00+00:00

Code

from collections import deque

def bfs(sy: int, sx: int, dist: list) -> list:
    INF = float('inf')
    d = ((0, 1), (0, -1), (1, 0), (-1, 0))
    q = deque()
    q.append((sy, sx))

    while q:
        vy, vx = q.popleft()
        for dy, dx in d:
            y = vy + dy
            x = vx + dx
            if not (0 <= x < w and 0 <= y < h):continue
            if grid[y][x] == '#': continue
            if dist[y][x] != INF: continue
            dist[y][x] = dist[vy][vx] + 1
            q.append((y, x))


    return dist

def main() -> None:
    global h, w, grid

    h, w = map(int, input().split())
    grid = [list(input()) for _ in range(h)]

    dist = bfs(0, 0)
    print(*dist, sep='\n')

if __name__ == "__main__":
    main()

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.5/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.5/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError