题目描述
LYK 陷进了一个迷宫！这个迷宫是网格图形状的。LYK 一开始在(1,1)位置，出口在(n,m)。
而且这个迷宫里有很多怪兽，若第 a 行第 b 列有一个怪兽，且此时 LYK 处于第 c 行 d 列，此
时这个怪兽对它的威胁程度为|a-c|+|b-d|。
LYK 想找到一条路径，使得它能从(1,1)到达(n,m)，且在途中对它威胁程度最小的怪兽的
威胁程度尽可能大。
当然若起点或者终点处有怪兽时，无论路径长什么样，威胁程度最小的怪兽始终=0。
输入格式(run.in)
第一行两个数 n,m。
接下来 n 行，每行 m 个数，如果该数为 0，则表示该位置没有怪兽，否则存在怪兽。
数据保证至少存在一个怪兽。
输入格式(run.out)
一个数表示答案。
输入样例
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。
思路：
预处理那部分写的差不多了，但没想二分，结果愣了半天也没做出来。。。
先预处理每个点到怪物的距离最小值（到最近怪物的距离），然后二分答案。
二分判断始终和怪物保持>=mid 的距离，能否到达终点。
#include<iostream> #include<cstdio> #include<queue> #include<vector> #include<cstring> #include<algorithm> using namespace std; int n,m,ans; int map[1009][1009]; int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0}; int vis[1009][1009]; struct node { int x;int y; int d; }; queue<node>Q; void work() { node now,o; int x;int y; while(!Q.empty()) { now=Q.front();Q.pop(); for(int i=0;i<=3;i++) { x=now.x+dx[i]; y=now.y+dy[i]; if(x<1||x>n) continue; if(y<1||y>m) continue; if(map[x][y]<= map[now.x][now.y]+1) continue; map[x][y]=map[now.x][now.y]+1; o.x=x,o.y=y; if(!vis[x][y]) { Q.push(o); vis[x][y]=1; } } } } bool check(int x) { queue<node>q; node now,o; now.x=1,now.y=1; memset(vis,0,sizeof(vis)); q.push(now); while(!q.empty()) { now=q.front();q.pop(); for(int i=0;i<=3;i++) { o.x=now.x+dx[i]; o.y=now.y+dy[i]; if(o.x<1||o.x>n) continue; if(o.y<1||o.y>m) continue; if((!vis[o.x][o.y])&&map[o.x][o.y]>=x) { vis[o.x][o.y]=1; q.push(o); } if(o.x==n&&o.y==m) return 1; } } return 0; } int main() { freopen("run.in","r",stdin); freopen("run.out","w",stdout); scanf("%d%d",&n,&m); memset(map,127,sizeof map); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { int c; scanf("%d",&c); if(c) { node now;now.x=i,now.y=j; Q.push(now),map[i][j]=0; } } work(); if((!map[1][1])||(!map[n][m])) { cout<<0; return 0; } int L=0,R=1200000,mid,ans; while(L<R-1) { mid=(R+L)>>1; if(check(mid)) { L=mid; ans=mid; } else R=mid-1; } for(int i=R+1;i>=L-1;i--) if(check(i)) { printf("%d",i); return 0; } return 0; }