[백준 1261] 알고스팟

from queue import PriorityQueue
import sys

def Dijkstra(G,sp):
    
    INF=float("inf")
    dist=[INF]
    prev=[0]
    Q=set()
    que=PriorityQueue()

    for i in range(1,len(G)):
        if i==sp:
            dist.append(0)
        else:
            dist.append(INF)
        prev.append(0)
        Q.add(i)
        que.put((dist[i],i))

    while Q!=set():
        while True:
            temp_u=que.get()[1]
            if temp_u in Q:
                u=temp_u
                break
        Q.remove(u)
        for i in range(1,len(G[u])+1):
            alt=dist[u]+G[u][i-1][1]
            if alt<dist[G[u][i-1][0]]:
                dist[G[u][i-1][0]]=alt
                prev[G[u][i-1][0]]=u
                que.put((alt,G[u][i-1][0]))
    
    return dist,prev

n,m=map(int, sys.stdin.readline().split())
v=n*m
G=[[] for _ in range(v+1)]
M=[sys.stdin.readline().rstrip() for _ in range(m)]

for i in range(n-1):
    for j in range(m):
        G[i+j*n+1].append((i+j*n+2,int(M[j][i+1])))

for i in range(n):
    for j in range(m-1):
        G[i+j*n+1].append((i+j*n+1+n,int(M[j+1][i])))

for i in range(1,n):
    for j in range(m):
        G[i+j*n+1].append((i+j*n,int(M[j][i-1])))

for i in range(n):
    for j in range(1,m):
        G[i+j*n+1].append((i+j*n+1-n,int(M[j-1][i])))

print(Dijkstra(G,1)[0][n*m])