大逃亡(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|。

【输入格式】

第一行3个整数为N，X，Y

第二行4个整数为x1,y1,x2,y2

下面将有N行，为N个敌人所在的坐标。

【输出格式】

在一行内输出你离敌人的距离及在这个距离的限制下，你到目标点最少要移动多少步。

【样例输入】

2 5 6

0 0 4 0

2 1

2 3

【样例输出】

2 14

 

由最大化最小值，我们可以想到二分。

然后每次距离需要预处理出来，我们很容易想到bfs。

二分答案检查可行性，最后得出最优解。

 

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;bool mark[1010][1010];int map[1010][1010];int heng[5000010],shu[5000010];int bs[1010][1010];int n,m,k,head,tail,qx,qy,zx,zy;int dx[4]={
    0,0,1,-1};int dy[4]={
    1,-1,0,0};void bfs(){    int i,nx,ny,xx,yy,p;    while(head<=tail)    {        xx=heng[head];        yy=shu[head];        head++;        for(p=0;p<4;p++)        {            nx=xx+dx[p];            ny=yy+dy[p];            if(nx<1||nx>n||ny<1||ny>m)               continue;            if(!mark[nx][ny])            {                mark[nx][ny]=1;                map[nx][ny]=map[xx][yy]+1;                tail++;                heng[tail]=nx;                shu[tail]=ny;            }        }       }}bool check(int mid){    int i,xx,yy,nx,ny,p;    head=1;    tail=1;    heng[1]=qx;    shu[1]=qy;    memset(mark,0,sizeof(mark));    memset(bs,127,sizeof(bs));    mark[qx][qy]=1;    bs[qx][qy]=0;    while(head<=tail)    {        xx=heng[head];        yy=shu[head];        head++;        for(p=0;p<4;p++)        {            nx=xx+dx[p];            ny=yy+dy[p];            if(nx<1||nx>n||ny<1||ny>m||map[nx][ny]
           
            >1; if(check(mid)) l=mid; else r=mid; } if(check(r)) { cout<
            
             <<" "<