[白俊]1261アルゴ駅
BFS+最短パス(複数本)
受け取った入力は文字列ですが、「1」ではなく「1」で、解答から誤った答えが出ました.
受け取った入力は文字列ですが、「1」ではなく「1」で、解答から誤った答えが出ました.
import heapq
dx=[0,1,0,-1]
dy=[1,0,-1,0]
width,height=map(int,input().split())
distance=[[-1]*width for _ in range(height)]
board=[]
for i in range(height):
board.append(input())
def dijackstra(x,y):
q=[]
heapq.heappush(q,(0,x,y))
while q:
cnt,x,y=heapq.heappop(q)
distance[x][y]=0
if x==height-1 and y==width-1:
print(cnt)
return
for i in range(4):
nx=dx[i]+x
ny=dy[i]+y
if nx<0 or ny<0 or nx>=height or ny>=width:
continue
if distance[nx][ny]!=-1:
continue
if board[nx][ny]=='1':
distance[nx][ny]=distance[x][y]+1
heapq.heappush(q,(cnt+1,nx,ny))
else:
distance[nx][ny]=distance[x][y]+1
heapq.heappush(q,(cnt,nx,ny))
dijackstra(0,0)
Reference
この問題について([白俊]1261アルゴ駅), 我々は、より多くの情報をここで見つけました https://velog.io/@code12/백준-1261-알고스팟テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol