/* 문제 */ N×M크기의 배열로 표현되는 미로가 있다. 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다. 위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.
최단 거리는 bfs를 통해 구할 수 있다. bfs에서는 현재 노드에서 가장 가까운 노드부터 방문한다. 즉 시작점에서 거리가 1인 노드들 -> 시작점에서 거리가 2인 노드들 -> 시작점에서 거리가 3인 노드들 ... -> 시작점에서 거리가 최대인 노드들 순으로 방문한다. bfs에서 만약 어떤 노드가 거리가 4인 노드들을 방문할 때 방문되었다면 그 노드에 이르는 최단 경로의 길이는 4인 것이다. 그 이하라면 앞의 단계에서 이미 방문되었을 것이다.
이 원리를 이용해 최단 경로의 길이를 구할 때는 각 노드의 시작점에서부터의 거리를 저장하는 distance 리스트를 만든다.
# 정답 코드
from collections import deque
import sys
input = sys.stdin.readline
def bfs(graph, x, y, dis):
global n, m
queue = deque([[x, y]])
graph[x][y] = 0 # 시작점 방문처리
dis[x][y] = 1 # 시작점 거리 1
while queue:
v = queue.popleft()
dx, dy = v[0], v[1]
if dx > 0 and graph[dx-1][dy] == 1:
queue.append([dx-1, dy])
graph[dx-1][dy] = 0 # 방문처리
dis[dx-1][dy] = dis[dx][dy] + 1
if dx < n-1 and graph[dx+1][dy] == 1:
queue.append([dx+1, dy])
graph[dx+1][dy] = 0 # 방문처리
dis[dx+1][dy] = dis[dx][dy] + 1
if dy > 0 and graph[dx][dy-1] == 1:
queue.append([dx, dy-1])
graph[dx][dy-1] = 0 # 방문처리
dis[dx][dy-1] = dis[dx][dy] + 1
if dy < m-1 and graph[dx][dy+1] == 1:
queue.append([dx, dy+1])
graph[dx][dy+1] = 0 # 방문처리
dis[dx][dy+1] = dis[dx][dy] + 1
n, m = map(int, input().split())
dis = [[0 for _ in range(m)] for _ in range(n)]
maze = []
for _ in range(n):
maze.append(list(map(int, list(input().strip()))))
bfs(maze, 0, 0, dis)
print(dis[n-1][m-1])
