【题解】刺杀大使

P1902 刺杀大使

Solution:二分答案+搜索

分析

既然是求最大值最小，容易想到二分答案，具体就是二分从第一行走到最后一行经过的最大值（假设为mid），用dfs检验，即只走小于等于mid的格子，看是否能到达最后一行
而这道题最有意思的是，vis数组在回溯时无需清空
为什么呢？因为我们关注的是可行性，如果第一次访问到一个点它无法到达最后一行，那么下一次换条路重新经过它，它依然无法到达最后一行
你可能会说可这两次访问的状态实际是不一样的（即vis数组），但你再想想，如果第二次访问这个点，存在一个解需要经过第一次访问中vis已经标记过的点的话，那么这个解一定可以在访问这个"vis已经标记过的点"的时候算出
综上所述，vis数组在回溯时无需清空

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;

inline int read()
{
	register int x=0,w=1;
	register char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if(ch=='-'){ch=getchar();w=-1;}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return x*w;
}
const int dirx[4]={-1,1,0,0},diry[4]={0,0,-1,1};
//queue<int>qx,qy;
int n,m,mid,f;
int mp[1005][1005],vis[1005][1005];
void dfs(int x,int y)
{
	if(f==1) return ;
	if(x==m) {
		f=1;
		return ;
	}
	for(int i=0;i<4;++i)
	{
		int xx=x+dirx[i],yy=y+diry[i];
		if(xx<1||yy<1||xx>n||yy>m) continue;
		if(vis[xx][yy]||mp[xx][yy]>mid) continue;
		vis[xx][yy]=1;
		dfs(xx,yy);
	}
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=n;++i)
      for(int j=1;j<=m;++j)
        mp[i][j]=read();
    int l=0,r=1005;
    while(l+1<r)
    {
    	memset(vis,0,sizeof vis);
    	mid=l+r>>1;
    	f=0;
		dfs(1,1);
		if(f) r=mid;
		else l=mid;
	}
	cout<<r<<endl;
	return 0;
}