#백준_2146 다리 만들기 - Java

# BFS 두 번 사용하여, 첫 번째에는 BFS를 통해 그룹화 시키고 두 번째에는 그룹화 된 배열을 가지고 BFS를 수행하며 최단거리를 구함

package bj;

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

public class p2146 {
	static int arr[][];
	static int graph[][];
	static int n;
	static int moveX[] = {0,1,0,-1};
	static int moveY[] = {-1,0,1,0};
	static boolean visit[][];
	static int cnt=1;
	static int rs=9999;
	static ArrayList<Point>[] arrList;
	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][n];
		visit = new boolean[n][n];
		graph = new int[n][n];
		arrList = new ArrayList[10001];
		for(int i=0; i<n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=0; j<n; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				if(arr[i][j] == 1 && !visit[i][j]) {
					arrList[cnt-1] = new ArrayList<>();
					make_graph(new Point(j,i), cnt);
					cnt++;
					
				}
			}
		}
//		for(int i=0; i<n; i++) {
//			for(int j=0; j<n; j++) {
//				System.out.print(graph[i][j] +" ");
//			}System.out.println();
//		}
		
		
		for(int i=0; i<cnt-1; i++) {
			bfs(arrList[i]);
		}
		System.out.println(rs);
		
	}
	public static void bfs(ArrayList<Point> ar) {
		visit = new boolean[n][n];
		Queue<Point> q = new LinkedList<>();
		int val = graph[ar.get(0).y][ar.get(0).x];
		
		for(int i=0; i<ar.size(); i++) {
			int x = ar.get(i).x;
			int y = ar.get(i).y;
			visit[y][x] = true;
			q.add(new Point(x,y));
		}
		int result=0;
		while(!q.isEmpty()) {
			int size = q.size();
			for(int i=0; i<size; i++) {
				Point p = q.poll();
				int x = p.x;
				int y = p.y;
				
				for(int d=0; d<4; d++) {
					int newY = y + moveY[d];
					int newX = x + moveX[d];
					if(0<=newX && newX<n && 0<=newY && newY<n) {
						if(graph[newY][newX]!=0 && graph[newY][newX] != val) {
							
							rs = Math.min(rs, result);
//							System.out.println(y+" "+x+ " // " +newY+" "+newX + " // "+result);
							return;
						}else if(graph[newY][newX]==0 && !visit[newY][newX]) {
							visit[newY][newX] = true;
							q.add(new Point(newX,newY));
						}
					}
				}
				
				
			}
			result++;
		}
	}
	public static void make_graph(Point p, int cnt) {
		
		Queue<Point> queue = new LinkedList<Point>();
		
		queue.add(p);
		
		while(!queue.isEmpty()) {
			Point tmp = queue.poll();
			
			int x = tmp.x;
			int y = tmp.y;
			arrList[cnt-1].add(new Point(x,y));
			
			visit[y][x] = true;
			graph[y][x] = cnt;
			
			for(int d=0; d<4; d++) {
				int newX = x + moveX[d];
				int newY = y + moveY[d];
				
				if(0<=newX && newX<n && 0<=newY && newY<n) {
					if(!visit[newY][newX] && arr[newY][newX]==1) {
						visit[newY][newX] = true;
						queue.add(new Point(newX,newY));
					}
				}
			}
			
		}
	}
}