미로 탈출

import java.util.*;

public class Main {
    public static int n;
    public static int m;
    //미로 정보 담긴 배열인데 거리도 기록할것임
    public static int[][] arr;
    public static int[] dx = {-1,1,0,0};
    public 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();
        kb.nextLine();
        arr = new int[n][m];

        for(int i = 0; i < n; i++) {
            String str = kb.nextLine();
            for(int j = 0; j < m; j++) {
                arr[i][j] = str.charAt(j) - '0';
            }
        }

        System.out.println(Arrays.deepToString(arr));
        System.out.println(BFS(0,0));

    }

    private static int BFS(int x, int y) {
        Queue<Point> q = new LinkedList<>();
        //첫 좌표 큐에 넣기
        q.offer(new Point(x, y));

        //큐가 빌때까지 반복하는데 각 좌표마다 거리를 계산한다.
        while (!q.isEmpty()) {
            Point tmp = q.poll();
            x = tmp.x;
            y = tmp.y;
            //해당 좌표의 상하좌우를 확인해서 이동
            for(int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                //이동가능한 곳이고 괴물이 없다면 이동시키기.
                if(nx >= 0 && ny >= 0 && nx < n && ny < m && arr[nx][ny] == 1) {
                    q.offer(new Point(nx, ny));
                    arr[nx][ny] = arr[x][y] + 1;
                }
            }
        }
        return arr[n - 1][m - 1];
    }

    private static class Point {
        public int x;
        public int y;
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}