【题解】[Nwerc 2006]escape -C++

概述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)。 在移动的过程中你当然希望离敌人的距离的最小值最大化，现在请求出这个值最大可以为多少,以及在这个前提下 你最少要走多少

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|。
input
第一行给出数字N，X，Y
第二行给出x1,y2
下面将有N行，给出N个敌人所在的坐标
Output
在一行内输出你离敌人的距离及在这个距离的限制下，你回到目标点最少要移动多少步。
Sample input

2 5 60 0 4 02 12 3

Sample Output

2 14

这周考试的第三题...
看起来很水但是做起来会发现没有思路
肯定要先构造一个原图（这个不用说）
我想的是用@H_403_32@best[i][j]来表示点（i,j）距离最近的敌人的距离。
但是我发现我只会用$O(nxy)$的时间复杂度预处理！！！
这个思路很简单，best数组初始值极大值，每次输入一对坐标就遍历一遍这个图，把@H_403_32@best[i][j]和敌人与点(i,j)的距离取min，然后就可以得到一张预处理过的图。
很明显，这玩意会炸：$N（1<=N<=10000），X（1<=x<=1000），Y（1<=Y<=1000）$。
$O(nxy)$原地爆炸好吗！！！
经过机房大佬细心开导 ，预处理用一个BFS来完成。
思路：输入坐标打入队列，然后和正常的BFS一样向周围扩散求得best值，因为BFS先遇到的肯定最优，所以这个方法只需要大概$O(x*y)$的时间复杂度就能完成预处理。
然后就是搜索过程emmm
搜索需要用二分来完成！！！！
与这道题类似的，把最终值拿来二分，下界0,上界是终点和起点的best值取min！因为起点和终点是一定会经过的，不妨用这个特性来缩小二分范围，然后用mID传入bfs搜索一波就行...具体二分过程不多讲解，不懂的可以看一下代码：

#include<bits/stdc++.h>#define FAST_IN std::ios::sync_with_stdio(false);cin.tIE(NulL);using namespace std;int x,y,n,sx,sy,ex,ey,step;inline int hl/*howlong*/(int a,int b,int c,int d){    return abs(a-c)+abs(b-d);}struct node{     int x,t;};int best[1010][1010];bool vis[1010][1010];int dir[4][2]={{1,0},{-1,{0,1},-1}};queue<node> s;voID bfs1(){    while(!s.empty())    {        node Now=s.front();        s.pop();        for(int i=0;i<4;i++)        {            int tx=Now.x+dir[i][0];            int ty=Now.y+dir[i][1];            if(tx>=0&&ty>=0&&tx<x&&ty<y&&!best[tx][ty])            {                best[tx][ty]=Now.t+1;                s.push((node){tx,ty,Now.t+1});            }        }    }}bool bfs(int left){    if(best[sx][sy]-1<left)return 0;    memset(vis,sizeof(vis));    queue<node> q;    q.push((node){sx,0});    vis[sx][sy]=1;    while(!q.empty())    {        node Now=q.front();        q.pop();        if(Now.x==ex&&Now.y==ey)        {            step=Now.t;            return 1;        }        for(int i=0;i<4;i++)        {            int tx=Now.x+dir[i][0],ty=Now.y+dir[i][1];            if(best[tx][ty]-1<left)continue;            if(!vis[tx][ty]&&best[tx][ty]-1>=left&&0<=tx&&tx<x&&0<=ty&&ty<y)            {                q.push((node){tx,Now.t+1});                vis[tx][ty]=1;            }        }    }    return 0;}int main(){    FAST_IN;    scanf("%d%d%d%d%d%d%d",&n,&x,&y,&sx,&sy,&ex,&ey);    for(int i=1;i<=n;i++)    {        int tx,ty;        scanf("%d%d",&tx,&ty);        best[tx][ty]=1;        s.push((node){tx,1});    }    bfs1();//  for(int i=0;i<x;i++)//  {//      for(int j=0;j<y;j++)//      {//          cout<<best[i][j];//      }//      cout<<endl;//  }    int l=0,r=best[ex][ey];    while(l<r)    {        int mID=(l+r)/2;        if(bfs(mID))l=mID+1;        else r=mID;    }    cout<<r-1<<" "<<step<<endl;    return 0;}

ov.

总结

以上是内存溢出为你收集整理的【题解】[Nwerc 2006]escape -C++全部内容，希望文章能够帮你解决【题解】[Nwerc 2006]escape -C++所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。