描述

给出数字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个敌人所在的坐标

输出

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

输入输出样例

输入样例1

2 5 60 0 4 02 12 3

输出样例1

2 14

解题思路

　　这道题呢，我是用的二分枚举和敌人最小值的距离，然后先预处理每一个点与最近的敌人点的距离，最后搜索就好了。

题解

1 #include
      
        2 using namespace std; 3 int k,n,m; 4 int qwe=0; 5 int x1,y_1,x2,y2,ans=0; 6 int mp[1005][1005];//每个点与最近的敌人的距离  7 bool flag[1005][1005]; 8 struct node{ 9     int x;10     int y;11     int t;12 };13 queue
       
         s;14 bool p=true;15 int dir[4][2]={
    0,1,0,-1,1,0,-1,0};16 void bfs1()//初始化每个点与最近的敌人的距离 17 {18     while(!s.empty())19     {20         node head=s.front();21         s.pop();22         for(int i=0;i<4;i++)23         {24             int tx=head.x+dir[i][0];25             int ty=head.y+dir[i][1];26             if(tx>=0&&ty>=0&&tx
        
         
           q;37     memset(flag,0,sizeof(flag));//初始化标记 38     q.push((node){x1,y_1,0});39     flag[x1][y_1]=true;40     if(mp[x1][y_1]-1
          
           =0&&ty>=0&&tx
           
            
             >k>>n>>m;67 cin>>x1>>y_1>>x2>>y2;68 for(int i=1;i<=k;i++)69 {70 int x,y;71 scanf("%d%d",&x,&y);72 mp[x][y]=1;//没有设置成0是因为后面搜索太麻烦 73 s.push((node){x,y,1});74 }75 bfs1();76 int l=0,r=min(mp[x1][y_1],mp[x2][y2]),mid;//这里的r不可能比起点或者终点距离敌人的最小值大 77 while(l