「NOIP模拟赛」大逃亡
给出数字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
题解
灌水完二分+bfs验证
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<map> #include<vector> #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int ans1,ans2; int head,tail; int n,X,Y; int x1,y1,x2,y2; int mp[1005][1005]; int x[1000005],y[1000005],step[1000005]; bool vis[1005][1005]; int xx[4]={1,-1,0,0},yy[4]={0,0,1,-1}; void pre() { while(head!=tail) { int nx=x[head],ny=y[head];head++; for(int k=0;k<4;k++) { int tx=nx+xx[k],ty=ny+yy[k]; if(tx>=X||ty>=Y||tx<0||ty<0||mp[tx][ty]!=-1)continue; mp[tx][ty]=mp[nx][ny]+1; x[tail]=tx;y[tail]=ty;tail++; } } } int bfs(int val) { head=0;tail=1; if(x1==x2&&y1==y2)return 0; memset(vis,0,sizeof(vis)); vis[x1][y1]=1;x[0]=x1;y[0]=y1; while(head!=tail) { int nx=x[head],ny=y[head],ns=step[head];head++; for(int k=0;k<4;k++) { int tx=nx+xx[k],ty=ny+yy[k]; if(tx>=X||ty>=Y||tx<0||ty<0||mp[tx][ty]<val||vis[tx][ty])continue; vis[tx][ty]=1; if(tx==x2&&ty==y2)return ns+1; x[tail]=tx;y[tail]=ty;step[tail]=ns+1;tail++; } } return -1; } int main() { //freopen("escape.in","r",stdin); //freopen("escape.out","w",stdout); memset(mp,-1,sizeof(mp)); n=read();X=read();Y=read(); x1=read();y1=read();x2=read();y2=read(); for(int i=1;i<=n;i++) { int a=read(),b=read(); mp[a][b]=0; x[tail]=a;y[tail]=b;tail++; } pre(); int l=0,r=mp[x1][y1]; while(l<=r) { int mid=(l+r)>>1; int t=bfs(mid); if(t==-1)r=mid-1; else l=mid+1,ans1=mid,ans2=t; } printf("%d %d\n",ans1,ans2); return 0; } |
计数器 9318679
OI 课件=>
OI 课件=>
啊咧。。。这个好像是球的序列的那个代码o(╯□╰)o