BOJ 2178

package boj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

/**
 * Created by mkhwang on 2021/04/02
 * Email : orange2652@gmail.com
 * Github : http://github.com/myeongkwonhwang
 */
public class Boj2178 {
    static int X;
    static int Y;
    static int maze[][];
    static int dist[][];
    static int [] dx = {1, 0, -1, 0}; //아래부터 반시계방향
    static int [] dy = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        X = Integer.parseInt(st.nextToken());
        Y = Integer.parseInt(st.nextToken());

        maze = new int[X][Y];
        dist = new int[X][Y];

        for (int i = 0; i < X; i++) {
            st = new StringTokenizer(br.readLine());
            String line = st.nextToken();
            for (int j = 0; j < Y; j++) {
                maze[i][j] = line.charAt(j) - '0';
                dist[i][j] = -1;
            }
        }

        dist[0][0] = 0;
        bfs(0,0);

        System.out.println(dist[X-1][Y-1]+1);
    }

    private static void bfs(int x, int y) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(x, y));
        while (!queue.isEmpty()){
            Node curr = queue.poll();
            for (int dir = 0; dir < 4; dir++) {
                int nx = curr.getX() + dx[dir];
                int ny = curr.getY() + dy[dir];
                if(nx < 0 || nx >= X || ny < 0 || ny >= Y) continue;
                if(dist[nx][ny] >= 0 || maze[nx][ny] == 0) continue;

                dist[nx][ny] = dist[curr.x][curr.y]+1;
                queue.add(new Node(nx, ny));
            }
        }
    }

    public static class Node {
        private int x;
        private int y;

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

        public int getX() {
            return x;
        }

        public int getY() {
            return y;
        }
    }
}