# https://www.acmicpc.net/problem/1261
import sys
import heapq
from collections import Counter , deque
sys.setrecursionlimit(100000)
dx = [-1,1,0,0]
dy = [0,0,-1,1]
M,N = map(int,input().split())
mirrors = [list(map(int,input())) for _ in range(N)]
dist = [[-1] * M for _ in range(N)]
q = deque()
dist[0][0] = 0
q.append((0,0,0))
ans = int(1e9)
while q :
x,y,d = q.popleft()
if x == N-1 and y == M -1 :
ans = min(ans,d)
continue
for k in range(4) :
nx,ny = x + dx[k] , y + dy[k]
if 0 <= nx < N and 0 <= ny < M :
if dist[nx][ny] != -1 and dist[nx][ny] <= d + mirrors[nx][ny] : continue
dist[nx][ny] = d + mirrors[nx][ny]
q.append((nx,ny,dist[nx][ny]))
print(dist[N-1][M-1])
'CodingTest' 카테고리의 다른 글
[Python][백준 2839번] 설탕배달 (0) | 2021.11.29 |
---|---|
[Python][백준 16389번] 행성연결 (0) | 2021.11.27 |
[Python][백준 12869 번] 뮤탈리스크 (0) | 2021.11.25 |
[Python][백준 15565 번] 강의실 배정 (0) | 2021.11.24 |
[Python][백준 11000번] 강의실 배정 (0) | 2021.11.23 |