描述 Description
给出数字 N（1<=N<=10000），X（1<=x<=1000），Y（1<=Y<=1000）, 代表有 N 个敌人分布一个 X 行 Y 列的矩阵上，矩形的行号从 0 到 X-1, 列号从 0 到 Y-1 再给出四个数字 x1,y1,x2,y2, 代表你要从点 (x1,y1) 移到(x2,y2)。在移动的过程中你当然希望离敌人的距离的最小值最大化，现在请求出这个值最大可以为多少, 以及在这个前提下，你最少要走多少步才可以回到目标点。注意这里距离的定义为两点的曼哈顿距离，即某两个点的坐标分为(a,b),(c,d), 那么它们的距离为 | a-c|+|b-d|。
输入格式 InputFormat
第一行给出数字 N，X，Y.
第二行给出 x1,y1,x2,y2.
下面将有 N 行，给出 N 个敌人所在的坐标。
输出格式 OutputFormat
在一行内输出你离敌人的距离及在这个距离的限制下，你回到目标点最少要移动多少步。
样例输入 SampleInput
2 5 6
0 0 4 0
2 1
2 3
样例输出 SampleOutput
2 14
来源 Source
2014-10-4 NOIP 模拟赛 by lwher
代码 Code
先 floodfill 出所有点到离其最近的敌人的距离，然后二分答案，spfa 判断可行性。
貌似用了太多 STL 了不开 O2 的话有一定几率会 T 掉几个点~~(>_<)~~
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
const int inf=0x7fffffff/27.11;
const int dx[4]={0,0,1,-1};
const int dy[4]={1,-1,0,0};
int i,j,t,n,m,l,r,k,z,y,x;
int a[1005][1005];
bool used[1005][1005];
deque < pair<int,int> > q;
deque < pair<pair<int,int>,int> > f;
int sx,sy,ex,ey,X,Y;
int ans,step;
inline void read(int &x)
{
x=0;char ch=getchar();
while (ch<'0' || ch>'9') ch=getchar();
while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
}
inline void floodfill()
{
int i,j,t,tx,ty;
while (!q.empty())
{
for (i=0;i<4;i++)
{
tx=q.front().first+dx[i];ty=q.front().second+dy[i];
if (tx<0 || tx>=X || ty<0 || ty>=Y) continue;
if (a[tx][ty]>a[q.front().first][q.front().second]+1)
{
a[tx][ty]=a[q.front().first][q.front().second]+1;
if (!used[tx][ty])
{
used[tx][ty]=true;
q.push_back(make_pair(tx,ty));
}
}
}
q.pop_front();
}
}
inline bool can(int s)
{
int i,j,t,tx,ty;
while (!f.empty()) f.pop_front();
memset(used,false,sizeof(used));
f.push_back(make_pair(make_pair(sx,sy),0));used[sx][sy]=true;
while (!f.empty())
{
for (i=0;i<4;i++)
{
tx=f.front().first.first+dx[i];ty=f.front().first.second+dy[i];
if (tx==ex && ty==ey)
{
step=f.front().second+1;
return true;
}
if (tx<0 || tx>=X || ty<0 || ty>=Y) continue;
if (a[tx][ty]<s) continue;
if (!used[tx][ty])
{
used[tx][ty]=true;
f.push_back(make_pair(make_pair(tx,ty),f.front().second+1));
}
}
f.pop_front();
}
return false;
}
int main()
{
freopen("escape.in","r",stdin);
freopen("escape.out","w",stdout);
read(n);read(X);read(Y);
read(sx);read(sy);read(ex);read(ey);
for (i=0;i<X;i++) for (j=0;j<Y;j++) a[i][j]=inf;
memset(used,false,sizeof(used));
for (i=1;i<=n;i++) read(x),read(y),q.push_back(make_pair(x,y)),a[x][y]=0,used[x][y]=true;
floodfill();
l=0;r=min(a[sx][sy],a[ex][ey]);
ans=step=0;
while (l<=r)
{
int mid=(l+r)>>1;
if (can(mid)) ans=mid,l=mid+1;
else r=mid-1;
}
printf("%d %d\n",ans,step);
return 0;
}