[백준] 미로탐색

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    static int[][] map;
    static int N, M;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);
        N = kb.nextInt();
        M = kb.nextInt();
        map = new int[N][M];

        for (int i = 0; i < N; i++) {
            String a = kb.next();
            for (int j = 0; j < M; j++) {
                map[i][j] = a.charAt(j) - '0';
            }
        }

        int result = bfs(0, 0);
        System.out.println(result);
    }

    public static int bfs(int x, int y) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[] {x, y});

        while (!queue.isEmpty()) {
            int[] now = queue.poll();
            int cX = now[0];
            int cY = now[1];

            for (int i = 0; i < 4; i++) {
                int nextX = cX + dx[i];
                int nextY = cY + dy[i];

                if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < M && map[nextX][nextY] == 1) {
                    map[nextX][nextY] = map[cX][cY] + 1;
                    queue.offer(new int[] {nextX, nextY});
                }
            }
        }

        return map[N - 1][M - 1];
    }
}