[BOJ] 1981. 배열에서 이동

import java.util.*;

public class Main {
	static int MAX = 100;
	static int N, Max_Value, Min_Value;
	static int MAP[][];
	static boolean Visit[][];
	static int dx[] = { 0, 0, 1, -1 };
	static int dy[] = { 1, -1, 0, 0 };
	static Scanner sc = new Scanner(System.in);
	static void Input() {
		Max_Value = -1;
		Min_Value = 500;
		N=sc.nextInt();
		MAP = new int[N][N];
		Visit=new boolean[N][N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				MAP[i][j] = sc.nextInt();
				if (MAP[i][j] > Max_Value) 
					Max_Value = MAP[i][j];
				
				if (MAP[i][j] < Min_Value) 
					Min_Value = MAP[i][j];
			}
		}
	}

static boolean BFS(int Diff)
{
	Queue<Pair> Q=new LinkedList<Pair>();
    for (int i = Min_Value; i <= Max_Value; i++)
    {
    	for(int j=0;j<Visit.length;j++) {
    		for(int k=0;k<Visit[0].length;k++) {
    			Visit[j][k]=true;
    		}
    	}
    	
        for (int j = 0; j < N; j++)
        {
            for (int k = 0; k < N; k++)
            {
                if (i <= MAP[j][k] && MAP[j][k] <= i + Diff) Visit[j][k] = false;
            }
        }
 
        Q.add(new Pair(0, 0));
 
        while (!Q.isEmpty())
        {
            int x = Q.peek().first;
            int y = Q.peek().second;
            Q.poll();
 
            if (Visit[x][y] == true) continue;
            Visit[x][y] = true;
 
            if (x == N - 1 && y == N - 1) return true;
 
            for (int j = 0; j < 4; j++)
            {
                int nx = x + dx[j];
                int ny = y + dy[j];
 
                if (nx >= 0 && ny >= 0 && nx < N && ny < N)
                {
                    Q.add(new Pair(nx, ny));
                }
            }
        }
    }
    return false;
}

	static void Solution() {
		int Start = 0;
		int End = Max_Value - Min_Value;
		int Mid;

		while (Start <= End) {
			Mid = (Start + End) / 2;
			if (BFS(Mid) == true)
				End = Mid - 1;
			else
				Start = Mid + 1;
		}
		System.out.println(End + 1);
	}

	static void Solve() {
		Input();
		Solution();
	}

	public static void main(String[] args) {
		Solve();
	}
	
	static class Pair {
		int first,second;
		Pair(int first,int second){
			this.first=first;
			this.second=second;
		}
	}
}