# Mountain Walking code cpp

Ann
c_cpp
a year ago
2.1 kB
0
Indexable
Never
```#include <iostream>
#define MAX 10000
using namespace std;

struct Point{
int x,y;
};

class Queue{
public:
Point data[MAX];
int rear,front;

Queue(){
rear=0;
front=0;
}
bool IsEmpty(){
return rear==front;
}
bool IsFull(){
return front==(rear+1)%MAX;
}
void enQueue(int a,int b){
if(!IsFull()){
rear=(rear+1)%MAX;
data[rear].x=a;
data[rear].y=b;
}
}
Point deQueue(){
if(!IsEmpty()){
front=(front+1)%MAX;
return data[front];
}else return Point();
}
};

bool danhdau[101][101];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,-1,1};

int main()
{
//freopen("input.txt","r",stdin);
int TC;
cin >> TC;
int mang[101][101];
for(int tc=1;tc<=TC;tc++)
{
int N;
cin >> N;
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
{
cin >> mang[i][j];
danhdau[i][j]=false;
}
int docaomax=0;
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
if(mang[i][j]>docaomax) docaomax=mang[i][j];
bool ans;
int l=0;
int r=docaomax;
while(l<=r)
{
int mid = (l+r)/2;
for(int k=0; k<=docaomax-mid; k++)
{
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
danhdau[i][j]=false;
int minx=k;
int maxx=k+mid;

Queue walk;
ans=false;
if(mang[1][1]>=minx && mang[1][1]<=maxx)
{
walk.enQueue(1,1);
danhdau[1][1]=true;
}
while(!walk.IsEmpty() && ans==false)
{
Point a=walk.deQueue();

for(int h=0;h<4;h++)
{
int newx=a.x + dx[h];
int newy=a.y + dy[h];

if(newx>=1 && newx<=N && newy>=1 && newy<=N && mang[newx][newy]>=minx && mang[newx][newy]<=maxx)
{
if(newx==N && newy==N)
{
ans=true;
break;
}
if(danhdau[newx][newy]==false)
{
danhdau[newx][newy]=true;
walk.enQueue(newx,newy);
}
}
}

}
if(ans) break;
}
if(ans) r = mid - 1;
else l = mid + 1;

}
cout << "#"<<tc<<" "<<l<<endl;
}
return 0;
}```