首页 > 代码库 > 第四届河南省省赛 走迷宫 二分+DFS

第四届河南省省赛 走迷宫 二分+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 105using namespace std;int Map[MAX][MAX],vis[MAX][MAX],v[4][2]={{1,0},{-1,0},{0,1},{0,-1}},n;bool check(int x,int y){    if(x>=1 && x<=n && y>=1 && 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=0;i<4;i++)    {        int next_x=x+v[i][0];        int next_y=y+v[i][1];        if(check(next_x,next_y) && (Map[next_x][next_y]<=maxn && Map[next_x][next_y]>=minn))        {            vis[next_x][next_y]=1;            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,0,sizeof(Map));        minn=INF;        maxn=-INF;        for(int i=1;i<=n;i++)        {            for(int j=1;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[1][1]);//首尾你无法避免,所以将其差的绝对值定为最左端        R=maxn-minn;        while(L<=R)//对差值进行二分查找        {            Mid=(L+R)/2;            int ok=0;            for(int i=minn;i<=maxn-Mid;i++)            {                if(Map[1][1] < i)                    break;                if(Map[1][1] > i+Mid)                    continue;                memset(vis,0,sizeof(vis));                if(DFS(1,1,i+Mid,i))                {                    ans=Mid;                    R=Mid-1;                    ok=1;                    break;                }            }            if(!ok)                L=Mid+1;        }        printf("%d\n",ans);    }    return 0;}
View Code

 

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