MTWALK - Mountain Walking
Tác giả: skyvn97
Ngôn ngữ: C++
#include<stdio.h>
//#include<conio.h>
#define MAX 111
int h[MAX][MAX];
int c[MAX][MAX];
int n;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int maxh,minh;
void init(void)
{
scanf("%d",&n);
int i,j;
maxh=0;
minh=1e5;
for (i=1;i<=n;i=i+1)
for (j=1;j<=n;j=j+1)
{
scanf("%d",&h[i][j]);
if (h[i][j]>maxh) maxh=h[i][j];
if (h[i][j]<minh) minh=h[i][j];
}
for (i=0;i<=n+1;i=i+1)
{
c[0][i]=2;
c[i][0]=2;
c[n+1][i]=2;
c[i][n+1]=2;
}
}
void DFS(int x,int y)
{
int i;
c[x][y]=1;
for (i=0;i<=3;i=i+1)
if (c[x+dx[i]][y+dy[i]]==0)
{
c[x+dx[i]][y+dy[i]]=1;
DFS(x+dx[i],y+dy[i]);
}
}
bool moveable(int min,int max)
{
int i,j;
for (i=1;i<=n;i=i+1)
for (j=1;j<=n;j=j+1)
{
if ((h[i][j]<min) || (h[i][j]>max))
c[i][j]=2;
else c[i][j]=0;
}
if (c[1][1]>0) return (false);
if (c[n][n]>0) return (false);
c[1][1]=1;
DFS(1,1);
if(c[n][n]==0) return (false);
return(true);
}
bool move(int d)
{
int i;
for (i=minh;i+d<=maxh;i=i+1)
if (moveable(i,i+d)) return (true);
return (false);
}
void process(void)
{
int l=0;
int r=maxh-minh;
int m;
while (l<=r)
{
if (l==r)
{
printf("%d",r);
return;
}
if (r-l==1)
{
if (move(l))
{
printf("%d",l);
return;
}
printf("%d",r);
return;
}
m=(l+r)/2;
if (move(m)) r=m;
else l=m+1;
}
}
int main(void)
{
//freopen("tmp.txt","r",stdin);
init();
process();
//getch();
}