原題連接：點擊打開鏈接
題意：從（1，1）點到（n，n）找一條路徑（只能上下左右走），使路徑上最大點與最小點差值最小。。
思路分析：
（1）：這題和我們以前做的迷宮題差別很大，以前做的一般就是求 最小步數或代價最小，一個dfs或bfs即可，而此題是求最大點與最小點差。 www.2cto.com
（2）：分析看出，一次dfs和bfs對我等弱菜來說顯然不可（大牛或許可以）。
（3）：若直接搜索，那些點該搜，那些點不該搜，顯然是沒法進行……
（4）：看數據范圍值在結果就在 （0,120 ）之間，我們就可假設一個當前答案搜索！！不斷更新。。
（5）：根據輸入的迷宮各點值 ，我們可以找出最大值 mmax 和最小值 mmin，若當前答案是0 ，那要最多要搜索mmax-0 -mmin次，第一次可以搜的點值區間在（mmin，mmin+0）；看是否能找出路……若不能，下次可以搜索的點值區間在（min+1，mmin+0+1）；看是否能找出路徑，……若不能，下次可以搜索點值區間在（min+2，min+0+2）……直到最後一次可搜索的點值區間是（mmax-0，mmax）……；在每次搜索中的，只要一次能搜到路徑，即說明當前答案是可行的。。特別注意：：該當前答案搜出的滿足該答案的路徑 是最大值和最小值差在 當前答案內！！並不是差就是當前答案。。
（6）：可以先求出mmax，mmin，得到答案范圍，（0，mmax-mmin）；可以先假設當前答案是 mmax-mmin 依次向0 搜索，中間搜不出滿足當前答案的路徑，那麼正確答案就出來了！！即當前 答案+1。若能就一直向前搜索，直到 -1。
（7）：（6）中的方法對於弱數據是可以ac的。。但是有沒有更高效率思路？？看（6）中每次搜索的當前答案，是線性的！！，那麼就可以用 二分 來枚舉當前答案，時間復雜度 log（mmax-mmin）不就更快了……
AC代碼：
[cpp]
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
int map[150][150],mmax,mmin,flag;
int n,sx[]={1,-1,0,0},zy[]={0,0,1,-1};
int loop[150][150];
void init()
{
int i,j;
mmax=-1;
mmin=999999;
memset(map,-1,sizeof(map));
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
scanf("%d",&map[i][j]);
mmax= max(mmax,map[i][j]);
mmin= min(mmin,map[i][j]);
}
}
void dfs(int x,int y,int L,int R)
{
if(flag) return;
if(x==n&&y==n) {flag=1;return;}
int i,j;
for(i=0;i<4;i++)
{
int xx=x+sx[i];
int xy=y+zy[i];
if(map[xx][xy]>=L&&map[xx][xy]<=R&&loop[xx][xy]==0)
{loop[xx][xy]=1;dfs(xx,xy,L,R);}
}
}
bool find(int k)
{
int i,j;
for(i=mmin;i<=mmax-k;i++)
{
flag=0;
if(map[1][1]<i||map[1][1]>i+k) continue;
if(map[n][n]<i||map[n][n]>i+k) continue;
memset(loop,0,sizeof(loop));
loop[1][1]=1;
dfs(1,1,i,i+k);
if(flag)
return true;
}
return false;
}
int find_answer()
{
int i,j,x=0,y=mmax-mmin;
while(x<y)
{
//printf("x,y--->> %d %d\n",x,y);
int mid=(x+y)/2;
if(find(mid))
{
//printf("mid----%d\n",mid);
y=mid;
}
else
x=mid+1;
}
return y;
}
int main()
{
//freopen("g:\\Input.txt","r",stdin);
//freopen("g:\\out.txt","w",stdout);
int m;
while(~scanf("%d",&n))
{
init();
m=find_answer();
printf("%d\n",m);
}
}
