#백준_2665 미로만들기 - Java 자바

# 유형 : 그래프 탐색

# 난이도 : 골드 4

# 벽을 최소한으로 부수고 목적지까지 가는 BFS문제

# 다음 가야할 좌표의 값이 현재 벽을 부순 개수보다 크다면 이동을 하고 작다면 이동하지 않는다.

package bj;
 
import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
 
public class p2665 {
    static int N;
    static int arr[][], map[][];
    static int moveX[] = {0,1,0,-1};
    static int moveY[] = {-1,0,1,0};
    static int maxValue = Integer.MAX_VALUE;
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N+1][N+1];
        map = new int[N+1][N+1];
        for(int i=1; i<=N; i++) {
            String str = br.readLine();
            for(int j=1; j<=N; j++) {
                arr[i][j] = str.charAt(j-1)-'0';
                map[i][j] = Integer.MAX_VALUE;
            }
        }
        bfs(1,1);
//        for(int i=1; i<=N; i++) {
//            for(int j=1; j<=N; j++) {
//                System.out.print(map[i][j]+" ");
//            }System.out.println();
//        }
        System.out.println(map[N][N]);
    }
    
    public static void bfs(int x, int y) {
        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(x,y));
        map[y][x] = 0;
        while(!queue.isEmpty()){
            Point p = queue.poll();
            
            for(int d=0; d<4; d++) {
                int newX = p.x + moveX[d];
                int newY = p.y + moveY[d];
                
                //범위안에 속하면서 다음 좌표가 갱신이 아직 안되어있거나 더 크다면 => 더 작은값으로 갱신할수 있다면 
                if(1<=newX && newX<=N && 1<=newY && newY<=N && map[newY][newX] > map[p.y][p.x]) {
                    if(arr[newY][newX] == 1) {
                        queue.add(new Point(newX, newY));
                        map[newY][newX] = map[p.y][p.x];
                    }else {
                        queue.add(new Point(newX, newY));
                        map[newY][newX] = map[p.y][p.x] + 1;
                    }
                }
            }
        }
    }
    
    
}