SP733 MTWALK - Mountain Walking 题解

原题目链接

看到题目就想到了dfs+剪枝

然后就想到了dfs有问题

例如这组数据

4-9-12
| | |
2-4-10

从4开始，到10结束

dfs会走$4 \to 2 \to 4 \to 10$，答案为8

然而很明显走$4 \to 9 \to 4 \to 10$更优，答案为6

当然你加一大堆玄学优化也是可以搜出正确答案的

这里不再多讲，而是提供另一种思路：

二分

$Q:$二分什么呢？

$A:$二分答案啊……这不是废话吗……

$Q:$我还不知道二分答案啊！关键是$check$函数怎么写！

$A:$这个时候我们就要祭出$dfs$大法了！

刚才还说dfs有问题现在就用

• check函数循环最小值，最大值用最小值+答案计算出

• 对整张表dfs，标记数值在最小值到最大值区间内的格子

• 若目标点被标记，返回true，否则继续循环，直到循环结束，返回false

代码如下

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=110,move[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int m[N][N],n,ans=0;
bool visit[N][N];
template<typename T>inline void read(T &x)//快读
{
	char ch=getchar();
	T f=1;
	x=0;
	while(!('0'<=ch&&ch<='9'))
	{
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	do
	{
		x=(x<<3)+(x<<1)+ch-48;
		ch=getchar();
	}while('0'<=ch&&ch<='9');
	x*=f;
}
void dfs(int x,int y,const int& sml,const int& big)//sml即为最小值，big即为最大值
{//dfs板子，不作过多解释
	if(visit[x][y])
		return;
	visit[x][y]=true;
	for(int i=0;i<4;i++)
	{
		int nx=x+move[i][0],ny=y+move[i][1];
		if(nx<1||nx>n||ny<1||ny>n)
			continue;
		if(m[nx][ny]<sml||m[nx][ny]>big)//若不在最小值到最大值区间内，则continue
			continue;
		dfs(nx,ny,sml,big);
	}
}
inline bool check(int x)//x即为要检验的答案
{
	for(int i=max(0,max(m[1][1],m[n][n])-x);i<=min(110-x,min(m[1][1],m[n][n]));i++)
    //最小值的初值：从起点和终点里取最大的（不然其中一个点必然不被标记），减去x，并且不为负数（和0取max）
    //退出循环判断：从起点和终点里取最小的（不然其中一个点必然不被标记），并和110-x取最小值（不然最大值就超出数据范围了），如果i大于这个值，则退出循环
	{
		memset(visit,0,sizeof(visit));
		dfs(1,1,i,x+i);//i为最小值，x+i为最大值
		if(visit[n][n])//如果终点被标记，则返回true
			return true;
	}
	return false;//若所有区间均尝试过仍没有返回，则返回false
}
int main()
{
	read(n);
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
			read(m[i][j]);
	int l=0,r=N;//二分模板
	while(l<=r)
	{
		int mid=l+r>>1;
		if(check(mid))
		{
			ans=mid;
			r=mid-1;
		}
		else
			l=mid+1;
	}
	printf("%d",ans);
	return 0;
}