黄学长模拟day1 大逃亡

时间：2021-12-10 19:38:18

给出数字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

/*

同bzoj热身赛，二维前缀和，灌水留坑

*/

#include<iostream>

#include<cstdio>

#include<string>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<queue>

using namespace std;

const int maxn = ,inf = ;

inline int read(){

    char ch=getchar();

    int f=,x=;

    while(!(ch>=''&&ch<='')){if(ch=='-')f=-;ch=getchar();};

    while(ch>=''&&ch<=''){x=x*+(ch-'');ch=getchar();};

    return x*f;

}

struct nd{

    int x;

    int y;

};

int p,n,m;

int ex[maxn],ey[maxn],xa,xb,ya,yb;

int flag,dis[][],vis[][];

short d[][],s[][];

int dx[] = {,,-,};

int dy[] = {,,,-};

bool emy[][];

inline bool jud(int x,int y,int t){

    if(x <  || y <  || x >= m || y >= n) return false;

    if(t == ) return true;

    t--;

    int tx=+x-y+t,ty=x+y+t,dx=+x-y-t,dy=x+y-t;

    if(ty>=n+m-) ty = n+m-;

    if(tx>=+m) tx = +m;

    int tot = s[ty][tx];

    if(dy>&&dx>-n) tot += s[dy-][dx-];

    if(dy>) tot -= s[dy-][tx];

    if(dx>-n) tot -= s[ty][dx-];

    if(tot) return false;

    else return true;

}

bool check(int t){

    if(!jud(xa,ya,t)) return false;

    flag++;

    for(int i = ;i <= n+;i++){

        for(int j = ;j <= m+;j++){

            dis[i][j] = inf;

        }

    }

    nd now,nxt;

    now.x = xa;

    now.y = ya;

    queue<nd> q;

    q.push(now);

    dis[ya][xa] = ;

    vis[ya][xa] = flag;

    while(!q.empty()){

        now = q.front();

        q.pop();

        //cout<<now.y<<" "<<now.x<<endl;

        for(int dr = ;dr < ;dr++){

            nxt.x = now.x + dx[dr];

            nxt.y = now.y + dy[dr];

            if(jud(nxt.x,nxt.y,t)&&vis[nxt.y][nxt.x] != flag){

                dis[nxt.y][nxt.x] = dis[now.y][now.x] + ;

                vis[nxt.y][nxt.x] = flag;

                q.push(nxt);

                if(nxt.y == yb && nxt.x == xb) return true;

            }

        }

    }

    return false;

}

int main(){

    freopen("escape.in","r",stdin);

    freopen("escape.out","w",stdout);

    cin>>p>>m>>n>>xa>>ya>>xb>>yb;

    for(int i = ;i <= p;i++){

        scanf("%d%d",&ex[i],&ey[i]);

        emy[ex[i]+ey[i]][+ex[i]-ey[i]] = true;

    }

    for(int i = ;i < n + m - ;i++){

        for(int j = -n;j < +m;j++){

            if(emy[i][j]) d[i][j] = d[i][j-] + ;

            else d[i][j] = d[i][j-];

        }

    }

    for(int i = ;i < n + m - ;i++){

        for(int j = -n;j < +m;j++){

            if(!i) s[i][j] = d[i][j];

            else s[i][j] = s[i-][j] + d[i][j];

        }

    }

    int l = ,r = n + m,mid,ans1,ans2;

    while(l <= r){

        mid = (l + r) >> ;

        if(check(mid)){

            ans1 = mid;

            ans2 = dis[yb][xb];

            l = mid + ;

        }else{

            r = mid - ;

        }

    }

    cout<<ans1<<" "<<ans2;

    return ;

}

相关文章