第四届河南省程序设计大赛 ——走迷宫（dfs+二分）

我会带着你远行 2022-02-12 11:04 213阅读 0赞

## 题目描述: ##

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

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

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

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

## 输入描述: ##

<span style="color:#000000">有多组测试数据，以EOF为输入结束的标志
    第一行：         N     表示迷宫是N*N方阵        (2≤ N≤ 100)
    接下来有N行，	每一行包含N个整数，用来表示每个单元格中难度 (0≤任意难度≤120)。</span>

## 输出描述: ##

<span style="color:#000000">	输出为一个整数，表示路径上最高难度与和最低难度的差。</span>

## 样例输入: ##

复制

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

## 样例输出: ##

单纯的dfs也能解这题，但是肯定会超时，这个题就是使用二分法依次找到用来剪枝的最大值最小值

这题是参考了网上一些大佬的做法，十分感谢！！！

ac代码：

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cmath>
    using namespace std;
    int book[101][101],a[101][101];   //book数组为标记数组，用来标记是否已经走过了 
    const int dir[4][2]={
       {0,1},{0,-1},{1,0},{-1,0}};   //用来标记上下左右 
    int flag,min1,max1,n;
    void dfs(int x,int y){   //定义dfs 
    	book[x][y]=1;
    	if(a[x][y]<min1||a[x][y]>max1)return ;   //若不符合这个区间则退出 
    	if(x==n-1&&y==n-1){
    		flag=1;
    		return ;  //若到达终点则将flag设置为1 
    	}
    	for(int k=0;k<4;k++){
    		int i=x+dir[k][0];
    		int j=y+dir[k][1];
    		if(i>=0&&i<n&&j>=0&&j<n&&!book[i][j]){   //dfs条件 
    			dfs(i,j);
    			if(flag)return ;   //若之前已成功到达终点，则直接退出 
    		}
    	}
    	return ;
    }
    bool xunzhao(int d){     //确定了差值为d 
    	for(int i=0;i+d<120;i++){    //遍历寻找可能出现的min以及max数值 
    		fill(book[0],book[0]+101*101,0);   //将标记数组归零 
    		min1=i;
    		max1=i+d;
    		flag=0;
    		dfs(0,0);    //进行dfs 
    		if(flag)return true;   //若flag为一则代表当前差值为d时是可以的 
    	}
    	return false;
    }
    void search(int l,int r){  //二分查找，l代表解得左边，r代表解的右边， 
    	while(l<=r){    
    		int mid=(l+r)/2;   
    		if(xunzhao(mid))r=mid-1;   //如果差值为mid时，是可以在途中找到一个路径的话，那么说明解可以更小，将r赋值等于mid 
    		else l=mid+1;        //如果无解，说明解比mid大一些，将l更新为mid 
    	}
    	cout<<l<<endl;
    	return ;
    }
    int main()
    {
    	while(scanf("%d",&n)!=EOF){
    		for(int i=0;i<n;i++){
    			for(int j=0;j<n;j++){
    				scanf("%d",&a[i][j]);
    			}
    		}
    		search(0,120);   //初始查询时，设置左边为0，右边为120 
    	}
    	return 0;
    }