[白俊]1261アルゴ駅


BFS+最短パス(複数本)
受け取った入力は文字列ですが、「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)