【题目描述】

山山来到了 CCF 城堡,这个城堡是一个 n*m 的迷宫。入口是城堡的左上角(1, 1),出

口是城堡的右下角(n, m)。 CCF 为了防止被太多的人膜拜,在城堡的某些小格中布置了陷阱,

有些没有。

这些陷阱是 CCF 专用的神奇的磁力装置。只要你所在的点与任何一个陷阱的曼哈顿距

离小于 k,就会被吸回起点(1, 1)。显然,当 k 值过大的时候,我们是永远不可能到达出口

(n, m)的。所以为了去膜拜 CCF,我们需要知道 k 最大能是多少。

【输入文件】

第一行三个正整数 n,m,c,表示迷宫的大小和陷阱的数量。

接下来 c 行,每行两个数,表示每个陷阱的坐标。数据保证陷阱坐标不超出迷宫。

【输出文件】

一个整数,能通关的最大 k 值。如果不能通关,输出 0。

【输入样例 1】

5 5 1

3 3

【输出样例 1】

2

【输入样例 2】

2 2 2

1 2

2 1

【输出样例 2】

0

【数据规模】

对于 60%的数据,

对于 100%的数据,

【hints】

(x1,y1) 和(x2,y2)的曼哈顿距离定义为|x1 - x2| + |y1 - y2|。

---

 

这题我们测的时候的数据比较水，各种二分都过了，我一开始也是用的二分，但是我写错了。

但是二分肯定不是正解，我最后用的是沈队教我的bfs过的。

首先我们看到这么多陷阱，想想怎么处理，我们可以先广搜一边，遍历一遍图，把每个点离最近的陷阱的曼哈顿距离算出来。

然后我们就会发现，从起点到终点的路径中只有离陷阱最近的距离有影响，

所以我们用ans记录从起点到该点的路径上距离陷阱最近的距离的最大值，

然后我们在bfs扫一遍，就可以输出答案了。

还要注意用循环队列防止运行错误。

代码：

 

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define ll long long#define il inline#define db doubleusing namespace std;il int gi(){	int x=0,y=1;	char ch=getchar();	while(ch<'0'||ch>'9')		{			if(ch=='-')				y=-1;			ch=getchar();		}	while(ch>='0'&&ch<='9')		{			x=x*10+ch-'0';			ch=getchar();		}	return x*y;}int n,m,c;int dist[5]={0,1,0,-1,0};int k[1000045][2];int headd,taill;int a,b,x,y;bool vis[1045][1045];int dis[1045][1045];il void bfs1(){	while(headd!=taill)		{			a=k[headd][0],b=k[headd++][1];			headd%=1000000;			for(int i=0;i<4;i++)				{					x=a+dist[i],y=b+dist[i+1];					if(x<1||y<1||x>n||y>m||vis[x][y])						continue;					vis[x][y]=1;					dis[x][y]=dis[a][b]+1;					k[taill][0]=x;					k[taill++][1]=y;					taill%=1000000;				}		}}int t[1000045][2];int head,tail=1;int ans[1045][1045];il void bfs2(){	memset(vis,0,sizeof(vis));	t[0][0]=1;	t[0][1]=1;	ans[1][1]=dis[1][1];	while(head!=tail)		{			a=t[head][0],b=t[head++][1];			head%=1000000;			for(int i=0;i<4;i++)				{					x=a+dist[i],y=b+dist[i+1];					if(x<1||y<1||x>n||y>m||ans[x][y]>=min(ans[a][b],dis[x][y]))						continue;					ans[x][y]=min(ans[a][b],dis[x][y]);					t[tail][0]=x;					t[tail++][1]=y;					tail%=1000000;				}		}}int main(){	freopen("maze.in","r",stdin);	freopen("maze.out","w",stdout);	memset(ans,-1,sizeof(ans));	n=gi(),m=gi(),c=gi();		for(int i=1;i<=c;i++)		{			x=gi(),y=gi();			vis[x][y]=1;			k[taill][0]=x;			k[taill++][1]=y;		}	bfs1();	bfs2();	printf("%d\n",ans[n][m]);	return 0;}