풀이

최단경로를 풀때, 다익스트라, 플루워드워셜도 있지만 이렇게 2차원그래프로 주어진 경우에는 bfs를 통해 많이 풀도록 한다.

from collections import deque

n, m = map(int, input().split())
array = []

for i in range(n):
    array.append(list(map(int, input())))

dx = [-1, 1, 0, 0]
dy = [0, 0 , -1, 1]

def bfs(x, y):
    q = deque()
    q.append((x, y))

    while q:
        nx, ny = q.popleft()

        for i in range(4):
            xx = nx + dx[i]
            yy = ny + dy[i]
            if xx < 0 or yy < 0 or xx >= n or yy >= m:
                continue
            if array[xx][yy] == 1:
                array[xx][yy] = array[nx][ny] + 1
                q.append((xx, yy))
bfs(0,0)
print(array[n-1][m-1])