import java.util.ArrayDeque;
import java.util.Queue;

class Solution {
   
    private static int[] xLoc = {0, 0, -1, 1};
    private static int[] yLoc = {-1, 1, 0, 0};

    public static int solution(int[][] maps) {
        int n = maps.length;
        int m = maps[0].length;

        // 적진의 상, 좌 체크
        boolean canAttack = false;
        if (n - 2 >= 0 && maps[n - 2][m - 1] == 1) {
            canAttack = true;
        }
        if (!canAttack && m - 2 >= 0 && maps[n - 1][m - 2] == 1) {
            canAttack = true;
        }

        // 적진을 공격할 수 있다면 최소 거리 확인
        int answer = -1;
        if (canAttack) {
            answer = bfs(maps, n, m);
        }

        return answer;
    }

    private static int bfs(int[][] maps, int n, int m) {
        boolean[][] visited = new boolean[n][m];
        Queue<Location> queue = new ArrayDeque<>();

        queue.add(new Location(0, 0, 1));
        visited[0][0] = true;

        while (!queue.isEmpty()) {
            Location location = queue.poll();

            for (int i = 0; i < 4; i++) {
                int xx = location.x + xLoc[i];
                int yy = location.y + yLoc[i];

                if (xx >= 0 && xx < n && yy >= 0 && yy < m && !visited[xx][yy] && maps[xx][yy] == 1) {
                    int distance = location.distance + 1;

                    if (xx == n - 1 && yy == m - 1) {
                        return distance;
                    }

                    queue.add(new Location(xx, yy, distance));
                    visited[xx][yy] = true;
                }
            }
        }

        return -1;
    }
}


class Location {
    int x;
    int y;
    int distance;

    public Location(int x, int y, int distance) {
        this.x = x;
        this.y = y;
        this.distance = distance;
    }
}