Description

Dr.Kong设计的机器人卡多非常爱玩，它常常偷偷跑出实验室，在某个游乐场玩之不疲。这天卡多又跑出来了，在SJTL游乐场玩个不停，坐完碰碰车，又玩滑滑梯，这时卡多又走入一个迷宫。整个迷宫是用一个N * N的方阵给出，方阵中单元格中填充了一个整数，表示走到这个位置的难度。

这个迷宫可以向上走，向下走，向右走，向左走，但是不能穿越对角线。走迷宫的取胜规则很有意思，看谁能更快地找到一条路径，其路径上单元格最大难度值与最小难度值之差是最小的。当然了，或许这样的路径不是最短路径。

     机器人卡多现在在迷宫的左上角（第一行，第一列）而出口在迷宫的右下角（第N行，第N列）。

卡多很聪明，很快就找到了这样的一条路径。你能找到吗？

Input

有多组测试数据，以EOF为输入结束的标志

第一行： N 表示迷宫是N*N方阵 (2≤ N≤ 100)

接下来有N行， 每一行包含N个整数，用来表示每个单元格中难度 (0≤任意难度≤120)。

Output

输出为一个整数，表示路径上最高难度与和最低难度的差。

Sample Input

5

1 1 3 6 8

1 2 2 5 5

4 4 0 3 3

8 0 2 3 4

4 3 0 2 1

Sample Output

2

 

这题放了很久了，以前用dfs暴搜总是超时，也想不到什么好的剪枝方法，所以一直没A，今天突然想到可以用二分来枚举难度差，用dfs来判断能否在给定的难度差下完成任务，这样处理后复杂度骤降，自然也就AC了。

#include 
       
        #include 
        
         #define MIN(a,b) ((a)<(b)?(a):(b))#define MAX(a,b) ((a)>(b)?(a):(b))#define N 100int dx[4]={
     0,0,1,-1};int dy[4]={
     1,-1,0,0};int map[N][N],vis[N][N];int n,L,H;int small,big;bool success;void dfs(int x,int y){    int i,nx,ny;    if(map[x][y]
         
          H)  return;    if(x==n-1 && y==n-1)    {        success=true;        return;    }    for(i=0;i<4;i++)    {        nx=x+dx[i];        ny=y+dy[i];        if(nx<0 || nx>=n || ny<0 || ny>=n || vis[nx][ny])  continue;        vis[nx][ny]=1;        dfs(nx,ny);    }}bool judge(int d){    int i;    for(i=small;i+d<=big;i++)    {        L=i;        H=i+d;        success=false;        memset(vis,0,sizeof(vis));        vis[0][0]=1;        dfs(0,0);        if(success) break;    }    if(i+d<=big)    return true;    return false;}int main(){    int i,j;    int min,max,mid;    while(~scanf("%d",&n))    {        small=120;        big=0;        for(i=0;i
          
           >1;            if(judge(mid))  max=mid;            else    min=mid;        }        printf("%d\n",max);    }    return 0;}