## 의사코드 ##
# 최소 칸 수 -> BFS
#from collections import deque
# N×M크기의 배열인 미로
# graph = [list(map(int, sys.stdin.readline().strip())) for _ in range(n)]
# 방문 처리 배열
# visited = [[0] * m for _ in range(n)]
# 상하좌우
# dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
# 시작 노드를 큐에 삽입하고 방문처리
# queue = deque([(0, 0)])
# visited[0][0] = 1
# 큐에 삽입된 순서대로 x, y 꺼내서 방문하지 않은 노드를 방문 처리 후 큐에 삽입
# while queue:
# x, y = queue.popleft()
# for i in range(4):
# nx = x + dx[i]
# ny = y + dy[i]
# if 0 <= nx < n and 0 <= ny < m:
# if visited[nx][ny] == 0 and graph[nx][ny] == 1:
# visited[nx][ny] = visited[x][y] + 1
# queue.append((nx, ny))
통과한 코드
import sys
from collections import deque
n, m = map(int, input().split())
# N×M크기의 배열인 미로
graph = [list(map(int, sys.stdin.readline().strip())) for _ in range(n)]
# 방문 처리 배열
visited = [[0] * m for _ in range(n)]
# 상하좌우
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
# 시작 노드 추가
queue = deque([(0, 0)])
# 현재 노드 방문 처리
visited[0][0] = 1
# 큐가 완전히 빌 때까지 반복
while queue:
# 큐에 삽입된 순서대로 꺼내기
x, y = queue.popleft()
# (N, M)에 도착하면 최소 칸의 수 출력
if x == n-1 and y == m-1:
print(visited[x][y])
break
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < m:
# 아직 방문되지 않았고 이동할 수 있는 칸이면 방문 처리
if visited[nx][ny] == 0 and graph[nx][ny] == 1:
visited[nx][ny] = visited[x][y] + 1
queue.append((nx, ny))