BOJ 1261アルゴ駅
10771 ワード
https://www.acmicpc.net/problem/1261
時間1秒、メモリ128 MB
input :横M、縦N(1≦N、M≦100) 0は空き部屋、1は壁 を表します(1,1)および(N,M)は常に貫通する
output : 出力 条件:一部の部屋が移動可能な部屋は上下左右に隣接する空き部屋 です
bfsの問題が外線だとは知らなかったが、抱きしめただけだ.少なくとも壁を破らなければならないので、正しいのではないでしょうか...
例外はない.
毎日歩き続けるとき.
nx>n,ny>mなのでエラーになります.
=を含めると、グラフの外に表示されないようになります.
関数の動作は、次の移動する点に壁があるかどうかです.
あなたはもうその場所に行ったことがありません.
visit[x][y]+1今回は壁の存在により穿孔回数が増加
visit[nx][ny]の値より小さい場合はqに追加します.
壁がないときも上記の方法を繰り返します.
時間1秒、メモリ128 MB
input :
output :
bfsの問題が外線だとは知らなかったが、抱きしめただけだ.少なくとも壁を破らなければならないので、正しいのではないでしょうか...
例外はない.
毎日歩き続けるとき.
nx>n,ny>mなのでエラーになります.
=を含めると、グラフの外に表示されないようになります.
関数の動作は、次の移動する点に壁があるかどうかです.
あなたはもうその場所に行ったことがありません.
visit[x][y]+1今回は壁の存在により穿孔回数が増加
visit[nx][ny]の値より小さい場合はqに追加します.
壁がないときも上記の方法を繰り返します.
import sys
from _collections import deque
m, n = map(int, sys.stdin.readline().split())
graph = []
for i in range(n):
graph.append(list(map(int, sys.stdin.readline().strip())))
visit = [[99999] * m for i in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs():
q = deque([])
q.append((0, 0))
visit[0][0] = 0
while q:
x, y = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx >= n or nx < 0 or ny >= m or ny < 0:
continue
# 다음 이동하는 곳에 벽이 존재.
if graph[nx][ny] == 1:
if visit[nx][ny] == 99999 or visit[nx][ny] > visit[x][y] + 1:
visit[nx][ny] = visit[x][y] + 1
q.append((nx, ny))
else:
if visit[nx][ny] == 99999 or visit[nx][ny] > visit[x][y]:
visit[nx][ny] = min(visit[nx][ny], visit[x][y])
q. append((nx, ny))
bfs()
print(visit[n - 1][m - 1])Reference
この問題について(BOJ 1261アルゴ駅), 我々は、より多くの情報をここで見つけました https://velog.io/@jsin2475/BOJ-1261-알고스팟テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol