import java.util.*;
import java.io.*;
/* baekjoon 2206 */
public class Move {
public static class Location {
int r;
int c;
int distance; // 현재까지 이동한 거리
boolean isCrash; // 벽을 부쉈는지 확인
public Location(int r, int c, int distance, boolean isCrash) {
this.r = r;
this.c = c;
this.distance = distance;
this.isCrash = isCrash;
}
}
static int N;
static int M;
static int[][] map;
static boolean[][][] visited; // 벽을 부순 경우와 벽을 부수지 않은 경우의 방문 여부 확인
static int[][] canMove = {
{ -1, 0 },
{ 1, 0 },
{ 0, -1 },
{ 0, 1 },
};
static Queue<Location> queue;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
queue = new LinkedList<>();
map = new int[N][M];
visited = new boolean[N][M][2];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
String[] mapElements = st.nextToken().split("");
for (int j = 0; j < M; j++)
map[i][j] = Integer.parseInt(mapElements[j]);
}
bfs(0, 0, false);
}
public static void bfs(int r, int c, boolean isCrash) {
queue.add(new Location(r, c, 1, isCrash));
visited[r][c][0] = true;
while (!queue.isEmpty()) {
Location current = queue.poll();
// 현재 위치가 (N, M) 이면 종료
if (current.r == N - 1 && current.c == M - 1) {
System.out.println(current.distance);
return;
}
for (int i = 0; i < canMove.length; i++) {
int nextR = current.r + canMove[i][0];
int nextC = current.c + canMove[i][1];
if ((0 <= nextR && nextR < N) && (0 <= nextC && nextC < M)) {
if (map[nextR][nextC] == 0) { // 벽이 아니면
if (current.isCrash && !visited[nextR][nextC][1]) { // 벽을 부순적이 있으면
visited[nextR][nextC][1] = true;
queue.add(new Location(nextR, nextC, current.distance + 1, current.isCrash));
} else if (!current.isCrash && !visited[nextR][nextC][0]) { // 부순 적이 없으면
visited[nextR][nextC][0] = true;
queue.add(new Location(nextR, nextC, current.distance + 1, current.isCrash));
}
} else { // 벽이면
if (!current.isCrash) { // 벽을 부순다
visited[nextR][nextC][1] = true;
queue.add(new Location(nextR, nextC, current.distance + 1, true));
}
}
}
}
}
// 이동 못할 경우
System.out.println("-1");
}
}
visited 배열을 3차원으로 구현할 생각이 나지 않아 오랫동안 고민을 했다. 여러 형태에 대해서 좀 더 열린 생각을 할 수 있도록 하자!