第四届河南省省赛 走迷宫 二分+DFS

题目思路：使用二分查找路径中最大值和最小值之间的差值，从而确定出一组minn和maxn，对此组的minn和maxn经行DFS，如果可以找到一条路径，其中的最大值，最小值在minn~maxn的范围内，则查找成功。继续向左查找，否则向右查找

#include<iostream>

#include<algorithm>

#include<cstring>

#include<vector>

#include<stdio.h>

#include<queue>

#include<math.h>

#define INF 0x3f3f3f3f

#define MAX 105

using namespace std;

int Map[MAX][MAX],vis[MAX][MAX],v[][]={{,},{-,},{,},{,-}},n;

bool check(int x,int y)

{

    if(x>= && x<=n && y>= && y<=n && !vis[x][y])

        return true;

    return false;

}

bool DFS(int x,int y,int maxn,int minn)//深搜，若搜索过程中未发现 超越minn 和 maxn的值则搜索成功

{

    if(x==n && y==n)

        return true;

    for(int i=;i<;i++)

    {

        int next_x=x+v[i][];

        int next_y=y+v[i][];

        if(check(next_x,next_y) && (Map[next_x][next_y]<=maxn && Map[next_x][next_y]>=minn))

        {

            vis[next_x][next_y]=;

            if(DFS(next_x,next_y,maxn,minn))

                return true;

        }

    }

    return false;

}

int main()

{

    int L,R,Mid,maxn,minn,ans;

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

    {

        memset(Map,,sizeof(Map));

        minn=INF;

        maxn=-INF;

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

        {

            for(int j=;j<=n;j++)

            {

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

                minn=min(minn,Map[i][j]);

                maxn=max(maxn,Map[i][j]);

            }

        }

        L=abs(Map[n][n]-Map[][]);//首尾你无法避免，所以将其差的绝对值定为最左端

        R=maxn-minn;

        while(L<=R)//对差值进行二分查找

        {

            Mid=(L+R)/;

            int ok=;

            for(int i=minn;i<=maxn-Mid;i++)

            {

                if(Map[][] < i)

                    break;

                if(Map[][] > i+Mid)

                    continue;

                memset(vis,,sizeof(vis));

                if(DFS(,,i+Mid,i))

                {

                    ans=Mid;

                    R=Mid-;

                    ok=;

                    break;

                }

            }

            if(!ok)

                L=Mid+;

        }

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

    }

    return ;

}