首页 > 代码库 > 东北育才 day6
东北育才 day6
大逃亡(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<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>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]<mid) continue; if(!mark[nx][ny]) { mark[nx][ny]=1; bs[nx][ny]=bs[xx][yy]+1; tail++; heng[tail]=nx; shu[tail]=ny; } } } if(mark[zx][zy]) return 1; else return 0;}int main(){ //freopen("escape.in","r",stdin); //freopen("escape.out","w",stdout); int i,a,b,l=0,r,mid; scanf("%d%d%d",&k,&n,&m); head=1; tail=0; scanf("%d%d%d%d",&qx,&qy,&zx,&zy); qx++; qy++; zx++; zy++; for(i=1;i<=k;i++) { scanf("%d%d",&a,&b); a++; b++; tail++; heng[tail]=a; shu[tail]=b; mark[a][b]=1; } bfs(); r=map[qx][qy]; while(l+1<r) { mid=(l+r)>>1; if(check(mid)) l=mid; else r=mid; } if(check(r)) { cout<<r<<" "<<bs[zx][zy]; } else { check(l); cout<<l<<" "<<bs[zx][zy]; }}
东北育才 day6
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。