快跑！（广度优先搜索+二分）

广度优先搜索+二分）"/>

快跑！（广度优先搜索+二分）

快跑！

题目描述：
LYK 陷进了一个迷宫！这个迷宫是网格图形状的。 LYK 一开始在(1,1)位置，出口在(n,m)。
而且这个迷宫里有很多怪兽，若第 a 行第 b 列有一个怪兽，且此时 LYK 处于第 c 行 d 列，此
时这个怪兽对它的威胁程度为|a-c|+|b-d|。
LYK 想找到一条路径，使得它能从(1,1)到达(n,m)，且在途中对它威胁程度最小的怪兽的威胁程度尽可能大。
当然若起点或者终点处有怪兽时，无论路径长什么样，威胁程度最小的怪兽始终=0。
输入格式：
第一行两个数 n,m。
接下来 n 行，每行 m 个数，如果该数为 0，则表示该位置没有怪兽，否则存在怪兽。
数据保证至少存在一个怪兽。
输入格式：
一个数表示答案。
输入样例
3 4
0 1 1 0
0 0 0 0
1 1 1 0
输出样例
1
数据范围
对于 20%的数据 n=1。
对于 40%的数据 n<=2。
对于 60%的数据 n,m<=10。
对于 80%的数据 n,m<=100。
对于 90%的数据 n,m<=1000。
对于另外 10%的数据 n,m<=1000 且怪兽数量<=100。
思路：
首先预处理出每个点到最近的怪物的距离
BFS即可(刚开始把所有的怪物全部进队然后bfs)
然后二分答案求解

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=1010;
int n,m,tot,a[maxn][maxn],v[maxn][maxn];
int xx[5]={0,1,-1,0,0},yy[5]={0,0,0,1,-1};
queue<int> x,y;
bool flag[maxn][maxn];
void color()
{while(!x.empty()){int fx=x.front();int fy=y.front();x.pop();y.pop();for(int i=1;i<=4;i++){int tx=fx+xx[i];int ty=fy+yy[i];if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&!flag[tx][ty]){flag[tx][ty]=1;v[tx][ty]=v[fx][fy]+1;x.push(tx);y.push(ty);}}}
}
bool can(int mid)
{for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)flag[i][j]=0;while(!x.empty()) x.pop();while(!y.empty()) y.pop();x.push(1);y.push(1);flag[1][1]=1;while(!x.empty()){int fx=x.front();int fy=y.front();x.pop(),y.pop();for(int i=1;i<=4;i++){int tx=fx+xx[i],ty=fy+yy[i];if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&!flag[tx][ty]&&!a[tx][ty]&&v[tx][ty]>=mid){if(tx==n&&ty==m)return 1;flag[tx][ty]=1;x.push(tx);y.push(ty);}}}return 0;
}
int main()
{freopen("run.in","r",stdin);freopen("run.out","w",stdout);scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){cin>>a[i][j];if(a[i][j]==1){x.push(i);y.push(j);flag[i][j]=1;v[i][j]=0;}}color();if(a[1][1]==1||a[n][m]==1){cout<<0;return 0;}int l=0,r=m*n,mid,ans=0;while(l<=r){mid=(l+r)>>1;if(can(mid)){ans=mid;l=mid+1;}else r=mid-1;}cout<<ans;fclose(stdin);fclose(stdin);return 0;
}