RT,BFS TLE 60pts

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while (ch<'0'||ch>'9'){
		if (ch=='-')
			f=-1;
		ch=getchar();
	}
	while (ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+ch-48;
		ch=getchar();
	}
	return x*f;
}
int n=read(),a[1005][1005],maxi=-1e9,mini=1e9;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
struct node{
	int x,y;
};
bool vis[1005][1005];
int bfs(int x,int y,int w){
	int sum=1;
	queue<node> q;
	q.push(node{x,y});
	memset(vis,false,sizeof(vis));
	vis[x][y]=true;
	while(q.empty()==false){
		node cur=q.front();
		q.pop();
		for(int i=0; i<4; i++){
			int nx=cur.x+dx[i],ny=cur.y+dy[i];
			if(nx>=1&&nx<=n&&ny>=1&&ny<=n&&vis[nx][ny]==false&&abs(a[nx][ny]-a[cur.x][cur.y])<=w){
				vis[nx][ny]=true;
				sum++;
				q.push(node{nx,ny});
			}
		}
	}
	return sum;
}
bool check(int x){
	memset(vis,false,sizeof(vis));
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++)
			if(vis[i][j]==false&&bfs(i,j,x)>=n*n/2+n*n%2)
				return true;
	return false;
}
signed main(){
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++){
			int x=read();
			maxi=max(maxi,x);
			mini=min(mini,x);
			a[i][j]=x;
		}
	int lt=mini-1,rt=maxi+1;
	while(lt+1<rt){
		int mid=lt+rt>>1;
		if(check(mid)==true)
			rt=mid;
		else
			lt=mid;
	}
	cout<<rt;
	return 0;
}