题目描述
给出一个N行M列的地图，地图形成一个有N*M个格子的矩阵。地图中的空地用’.’表示。其中某些格子有怪兽，用’+’表示。某人要从起点格子’V’走到终点格子’J’，他可以向上、下、左、右四个方向行走。因此，起点和终点之间可以有许多条路径。注意：即使是有怪兽的格子，他也可以走上去。 设路径上某个格子的坐标为(R,C)，某个怪兽的坐标为(A,B)，那么它们之间的曼哈顿距离定义为：|R-A| + |C-B| 显然，地图上可能有许多怪兽，路径上也可能途经许多格子，每个格子到每个怪兽都可以算出之间的曼哈顿距离。 问整条路径中离怪兽的曼哈顿距离最小值最大为多少？
输入
输入格式： 第1行：2个整数N和M(1 ≤ N, M ≤ 500) 接下来N行，每行M个字符，可能是’.’, ‘+’, ‘V’, ‘J’等. 数据保证仅包含1个’V’ 和1个 ‘J’ ，至少有1个’+’
输出
输出格式： 第1行：1个整数，表示最短曼哈顿距离的最大值
样例输入
输入样例1：
4 4
+…
….
….
V..J
输入样例2
4 5
…..
.+++.
.+.+.
V+.J+
样例输出
输出样例一：
3
输出样例二：
0
一开始yy到了很多方法：
强行求出每个点到最近怪兽的曼哈顿距离，pass
BFS一波，pass
…………
左撞右撞，终于想到了一个正常的解法——二分答案
二分离怪兽的最短曼哈顿距离，将每个怪兽周围曼哈顿距离等于其的，标记一下，用BFS验证起点终点是否联通，来实现放缩
算了一下时间复杂度，
如果全屏怪兽，这种方法很危险，但没办法，数据好水哦，美滋滋~~~
代码如下：
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
struct node{
int x,y;
}mst[250001];
int m,n;
int map[501][501];
int sx,sy,ex,ey,cnt;
int u[4]={-1,1,0,0},z[4]={0,0,-1,1};
void getmap()
{
int i,j;
char c[501];
for(i=1;i<=m;i++)
{
scanf("%s",c+1);
for(j=1;j<=n;j++)
{
if(c[j]=='V')sx=i,sy=j;
if(c[j]=='J')ex=i,ey=j;
if(c[j]=='+')mst[++cnt].x=i,mst[cnt].y=j;
}
}
}
void work(int mhd)
{
for(int k=0;k<=mhd;k++)
for(int i=1;i<=cnt;i++)
{
if(mst[i].x+k>0&&mst[i].x+k<=m&&mst[i].y+(mhd-k)>0&&mst[i].y+(mhd-k)<=n)map[mst[i].x+k][mst[i].y+(mhd-k)]=1;
if(mst[i].x-k>0&&mst[i].x-k<=m&&mst[i].y+(mhd-k)>0&&mst[i].y+(mhd-k)<=n)map[mst[i].x-k][mst[i].y+(mhd-k)]=1;
if(mst[i].x+k>0&&mst[i].x+k<=m&&mst[i].y-(mhd-k)>0&&mst[i].y-(mhd-k)<=n)map[mst[i].x+k][mst[i].y-(mhd-k)]=1;
if(mst[i].x-k>0&&mst[i].x-k<=m&&mst[i].y-(mhd-k)>0&&mst[i].y-(mhd-k)<=n)map[mst[i].x-k][mst[i].y-(mhd-k)]=1;
}
}
bool bfs()
{
queue<int>Q[2];
Q[0].push(sx),Q[1].push(sy);
while(!Q[0].empty())
{
int x=Q[0].front(),y=Q[1].front();Q[0].pop(),Q[1].pop();
for(int i=0;i<4;i++)
if(x+u[i]>0&&x+u[i]<=m&&y+z[i]>0&&y+z[i]<=n&&!map[x+u[i]][y+z[i]])
{
if(x+u[i]==ex&&y+z[i]==ey)return 1;
map[x+u[i]][y+z[i]]=1;
Q[0].push(x+u[i]),Q[1].push(y+z[i]);
}
}
return 0;
}
int main()
{
int l=0,r=1<<30,mid;
scanf("%d%d",&m,&n);
getmap();
for(int i=1;i<=cnt;i++)
r=min(min(abs(sx-mst[i].x)+abs(sy-mst[i].y),abs(ex-mst[i].x)+abs(ey-mst[i].y)),r);
while(l<r)
{
memset(map,0,sizeof map);
mid=(l+r)>>1;
work(mid);
if(bfs())l=mid+1;
else r=mid;
}
printf("%d",l);
}