大逃亡(escape.*)
给出数字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|。
输入：
第一行给出数字N，X，Y
第二行给出x1,y1,x2,y2
下面将有N行，给出N个敌人所在的坐标
输出：
在一行内输出你离敌人的距离及在这个距离的限制下，你回到目标点最少要移动多少步。
Sample input
2 5 6
0 0 4 0
2 1
2 3
Sample output
2 14
sb搜索题
先跑一遍floodfill算出所有点到离它最近的敌人的距离
然后二分一个距离的最小值，再bfs一下，只能走距离>=mid的格子
唉因为二分上界打错了只有90
我做今天的模拟赛真是太逗了各种细节错还只有260……你看黄巨大又ak了
一定是因为我没睡醒
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 1010
#define ok (wx>=0&&wx<x&&wy>=0&&wy<y)
using namespace std;
const int mx[4]={1,0,-1,0};
const int my[4]={0,1,0,-1};
int dis[N][N];
int dis2[N][N];
bool mrks[N][N];
int qx[N*N],qy[N*N];
int n,x,y,x1,y1,x2,y2,t,w,ans,ds;
inline bool jud(int lim)
{
if (dis[x1][y1]<lim)return 0;
if (dis[x2][y2]<lim)return 0;
memset(mrks,0,sizeof(mrks));
memset(dis2,0,sizeof(dis2));
t=0;w=1;
qx[1]=x1;qy[1]=y1;
mrks[x1][y1]=1;
while (t<w)
{
int nx=qx[++t],ny=qy[t];
for (int k=0;k<4;k++)
{
int wx=nx+mx[k],wy=ny+my[k];
if (ok&&!mrks[wx][wy]&&dis[wx][wy]>=lim)
{
dis2[wx][wy]=dis2[nx][ny]+1;
mrks[wx][wy]=1;
qx[++w]=wx;
qy[w]=wy;
}
}
}
return mrks[x2][y2];
}
int main()
{
freopen("escape.in","r",stdin);
freopen("escape.out","w",stdout);
scanf("%d%d%d",&n,&x,&y);
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
for (int i=1;i<=n;i++)
{
int xx,yy;scanf("%d%d",&xx,&yy);
qx[++w]=xx;qy[w]=yy;
mrks[xx][yy]=1;
}
while (t<w)
{
int nx=qx[++t],ny=qy[t];
for (int k=0;k<4;k++)
{
int wx=nx+mx[k],wy=ny+my[k];
if (ok&&!mrks[wx][wy])
{
dis[wx][wy]=dis[nx][ny]+1;
mrks[wx][wy]=1;
qx[++w]=wx;
qy[w]=wy;
}
}
}
int l=0,r=x*y;
while (l<=r)
{
int mid=(l+r)>>1;
if (jud(mid)){ans=mid;ds=dis2[x2][y2];l=mid+1;}
else r=mid-1;
}
printf("%d %d\n",ans,ds);
}