NYOJ 306 走迷宫 [二分+搜索]

原题连接：点击打开链接
题意：从（1，1）点到（n，n）找一条路径（只能上下左右走），使路径上最大点与最小点差值最小。。

思路分析：
（1）：这题和我们以前做的迷宫题差别很大，以前做的一般就是求最小步数或代价最小，一个dfs或bfs即可，而此题是求最大点与最小点差。 www.zzzyk.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);
    }
}

补充：软件开发 , C++ ,