package code_test;
import java.util.*;
public class Main {
// 방향 이동 (상, 하, 좌, 우)
// 2차원 배열 0,0 부터 시작
// x 가 작아지고 y는 변동이 없어야 위로 감
private static final int[] dx = {-1, 1, 0, 0};
private static final int[] dy = {0, 0, -1, 1};
public static int bfs(int[][] maze, int n, int m) {
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{0, 0}); // 시작점 (0,0)에서 BFS 시작
boolean[][] visited = new boolean[n][m];
visited[0][0] = true;
while (!queue.isEmpty()) {
int[] current = queue.poll();
int x = current[0];
int y = current[1];
// 목표 지점에 도달하면 최소 칸 수를 반환
if (x == n - 1 && y == m - 1) {
return maze[x][y];
}
// 인접한 네 방향 탐색
for (int i = 0; i < 4; i++) {
// 현재 x y 에 상,하,좌,우 로 움직이는 좌표 설정
int nextX = x + dx[i];
int nextY = y + dy[i];
// 배열 인덱스가 마이너스가 아니고, 지정한 좌표 내 이거나, 통과 가능한 미로 이거나, 아직 방문하지 않은 칸이면
if (nextX >= 0 && nextY >= 0
&& nextX < n && nextY < m
&& maze[nextX][nextY] == 1
&& !visited[nextX][nextY]) {
// 큐에 상,하,좌,우 로 움직이는 좌표를 넣고
queue.add(new int[]{nextX, nextY});
// 해당 좌표를 방문처리 후
visited[nextX][nextY] = true;
// 재활용 한 배열에 이동거리 적산
maze[nextX][nextY] = maze[x][y] + 1; // 이동 거리를 1씩 늘려서 기록
}
}
}
return -1; // 도달할 수 없는 경우는 입력에 없으므로 여기에 도달하지 않음
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] maze = new int[n][m];
for (int i = 0; i < n; i++) {
String line = scanner.next();
for (int j = 0; j < m; j++) {
maze[i][j] = line.charAt(j) - '0';
}
}
// BFS를 통해 최소 칸 수를 구함
int result = bfs(maze, n, m);
System.out.println(result);
}
}