【題目描述】
山山來到了 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<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>#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;
}
i迷宮圖解。?
