白準2178号迷宮(BFS)へ移動

1514 ワード
白駿 BFS テキストリンク

質問:https://www.acmicpc.net/problem/2178

最短距離なのでBFSを使います。


再整理:
DFSスタックを使用した移動時の主な計算
BFSキューを使用して、主に最短距離を計算する
迷宮式の探索を行う場合は、上下左右の座標を設定します.
(このパターンを覚えておくべきだと思いますが…)
上下左右
dx = [-1,1,0,0]
dy = [0,0,-1,1]
入力値
N,M = map(int,input().split())
for i in range(N):
graph.append(list(map(int,input().strip())))
->MAP=[[int(i)for i in list(input()for in range(N)]が可能です.
stripではなくsplit()を使用すると、等しいまたは等しい
[[101111], [101010], [101011], [111011]]
stripの場合
[[1, 0, 1, 1, 1, 1], [1, 0, 1, 0, 1, 0], [1, 0, 1, 0, 1, 1], [1, 1, 1, 0, 1, 1]]
from collections import deque

def bfs(x,y):
    queue = deque()
    queue.append((x,y))

    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]

            if nx < 0 or nx >= N or ny < 0 or ny >= M:
                continue
            if graph[nx][ny] == 0:
                continue
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y]+1
                queue.append((nx,ny))
    return graph[-1][-1]
          #graph[N-1][M-1]

N,M = map(int,input().split())

graph = []

for i in range(N):
    graph.append(list(map(int,input().strip())))

dx = [-1,1,0,0]
dy = [0,0,-1,1]

print(bfs(0,0))
白駿A+B-7
[React] useEffect