nyoj 306 二分+dfs

#include<stdio.h>

#include<string.h>

#define N 200

int Min(int a,int b) {

return a>b?b:a;

}

int Max(int a,int b) {

return a>b?a:b;

}

int map[N][N],flag,visit[N][N],n,min,max;

int dis[4][2]={1,0,-1,0,0,1,0,-1};

void init() {

int i,j;

min=1000;

max=-1000;

for(i=1;i<=n;i++)

for(j=1;j<=n;j++) {

scanf("%d",&map[i][j]);

min=Min(min,map[i][j]);

max=Max(max,map[i][j]);

}

}

void dfs(int x,int y,int min,int max){

if(flag)return ;

if(x==n&&y==n){flag=1;return ;}

int i;

for(i=0;i<4;i++) {

int xx=x+dis[i][0];

int yy=y+dis[i][1];

if(map[xx][yy]>=min&&map[xx][yy]<=max&&visit[xx][yy]==0&&xx>=1&&xx<=n&&yy>=1&&yy<=n) {

visit[xx][yy]=1;

dfs(xx,yy,min,max);

}

}

}

int find_answer(int k) {

int i;

for(i=min;i<=max-k;i++) {

if(map[1][1]<i||map[1][1]>i+k)continue;

if(map[n][n]<i||map[n][n]>i+k)continue;

memset(visit,0,sizeof(visit));

visit[1][1]=1;

flag=0;

dfs(1,1,i,i+k);

if(flag==1)return 1;

}

return 0;

}

int slove(){

int mid,x=0,y=max-min;

while(x<y) {

mid=(x+y)/2;

if(find_answer(mid))

y=mid;

else

x=mid+1;

}

return y;

}

int main() {

while(scanf("%d",&n)!=EOF) {

init();

printf("%d\n",slove());

}

return 0;

}

巴特西

nyoj 306 二分+dfs

最新文章

热门文章