Untitled

unknown
plain_text
a year ago
2.1 kB
1
Indexable
Never
```// In Practice, You should use the statndard input/output
// in order to receive a score properly.
// Do not use file input and output. Please be very careful.

#include<iostream>

using namespace std;
#define size 1000000
int queue[size];
int front=-1;
int rear=-1;
int map[105][105];
int N;
int nho;
int lon;
bool visit[105][105];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,1,-1};
bool isEmpty(){
return front ==rear;
}
void push(int x){
if(rear==size-1) rear=-1;
rear++;
queue[rear]=x;
}
int pop(){
if(front==size-1) front=-1;
front++;
return queue[front];
}
void reset(){
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
visit[i][j]=false;
}

}

}
bool bfs(int l , int r){
front= rear=-1;
visit[0][0]=true;

push(0);
push(0);
if( map[0][0]<l || map[0][0]>r) return false;
else{
while(!isEmpty()){
int x=pop();
int y=pop();
for(int i=0; i<4; i++){
int x1= x+dx[i];
int y1= y+dy[i];
if(x1>=0 && x1<N && y1>=0 && y1<N && !visit[x1][y1] && map[x1][y1]>=l && map[x1][y1]<=r){
visit[x1][y1]=true;
push(x1);
push(y1);
if(x1==N-1 && y1==N-1){
return true;
}

}

}

}
}
return false;

}

bool check(int mid){
for(int i=nho ; i<= lon- mid; i++){
reset();
if(bfs(i, i+mid)) return true;
}
return false;
}

int tim(int l , int r){
int mid;
while(l!=r){
mid=(l+r)/2;
if(check(mid)) r=mid;
else l=mid+1;
}
return r;
}

int main(int argc, char** argv)
{
int test_case;
int T;

//freopen("text.txt", "r", stdin);
cin >> T;

/*
Read each test case from standard input.
*/
for(test_case = 1; test_case <= T; ++test_case)
{
lon=0;
nho=999;
int ans=0;
cin>>N;
for(int i=0; i<N;i++){
for(int j=0; j<N; j++){
cin>>map[i][j];
if(lon<map[i][j]){
lon=map[i][j];
}
if(nho>map[i][j]){
nho=map[i][j];
}

}
}
ans=tim(0,lon-nho);

cout << "#" << test_case << " " <<ans << endl;
}
return 0;//Your program should return 0 on normal termination.
}```