1 条题解
-
0
对格子进行二间隔染色。
首先观察吃子这一操作,有如下发现:
- 当双方初始位置同色时,每次轮到白方走时双方位置都同色,所以只有黑方可以吃白方;
- 当双方初始位置异色时,每次轮到黑方走时双方位置都同色,所以只有白方可以吃黑方。
两种情况相似,所以下面只介绍第一种情况的做法,第二种情况同理。
同时我们需要发现一个重要性质:双方的目标格之间的距离(指的是走马步的最少步数,下同)为 。
下面进行分析。当只有黑方能吃白方时,白方必胜的充要条件就是直接走向终点且能保证不被吃掉。容易发现白方能被黑方吃掉的充要条件是黑方能领先白方到达白方的目标格子。黑方到达白方目标格子时,双方位置同色,所以距离至少为 ,下一步白方走,距离只能变成 或 ,若变成 则黑方可以直接吃掉白方,否则,黑方只需要在 步之内直接走向自己的目标格即可。
根据上述分析,下面对第一种情况的分类进行总结:
- 若黑方能比白方更快到达自己的目标,就直接走向目标,由于白方不能吃黑方,所以黑方必胜;
- 若黑方能比白方更快到达白方的目标,就走向白方的目标,然后根据白方反应做出吃掉白方或者用 步走到自己目标的决定,黑方必胜;
- 否则,白方直接走向自己的目标,黑方能胜的情况已被前两种情况排除,所以白方必胜。
第二种情况同理。实现细节上:
- 用
bfs
求出黑白初始位置到黑白目标位置两两之间的距离和路径; - 注意交互细节,例如若选择黑方先手要先读入一次白方的坐标,若能吃掉对方就直接吃掉并结束程序;
- 注意每一处步数的比较是否取等都需要仔细思考。
时间复杂度 。
/** * @date: 2024.01.23 * @problem: CF1202E2 * @tags: 博弈论 */ #include<bits/stdc++.h> using namespace std; const int dx[8]={-2,-2,-1,-1,1,1,2,2}; const int dy[8]={-1,1,-2,2,-2,2,-1,1}; int n,m; struct Point{ int x,y; inline void read(){ cin>>x>>y; } inline void print(){ cout<<x<<' '<<y<<endl; } inline int type(){ return (x+y)&1; } inline bool operator==(Point t)const{ return x==t.x&&y==t.y; } inline Point to(int method){ return{x+dx[method],y+dy[method]}; } inline bool isOnlyOneStepTo(Point other){ if(abs(x-other.x)+abs(y-other.y)!=3)return false; return x!=other.x&&y!=other.y; } }W,B,tarW,tarB,other,myTar; void chooseWhite(){ cout<<"WHITE"<<endl; myTar=tarW; } void chooseBlack(){ cout<<"BLACK"<<endl; myTar=tarB; } struct Queue{ bool vis[1001][1001]; Point v[1000001]; int pre[1000001]; int step[1000001]; int head,tail; inline void clear(){ memset(vis,0,sizeof vis); head=1,tail=0; } inline void push(Point x,int prev,int s){ vis[x.x][x.y]=true; v[++tail]=x,step[tail]=s,pre[tail]=prev; } inline Point pop(){ return v[head++]; } void print(int id){ if(pre[id])print(pre[id]); else return; v[id].print(); if(other==v[id])exit(0); if(v[id]==myTar)exit(0); other.read(); } inline void print(){ print(this->head); } inline int bfs(Point S,Point T){ this->clear(); this->push(S,0,0); while(head<=tail){ Point x=v[head]; int s=step[head]; if(x==T)return s; for(int i=0;i<8;i++){ Point nxt=x.to(i); if(nxt.x<1||nxt.x>n||nxt.y<1||nxt.y>m)continue; if(vis[nxt.x][nxt.y])continue; this->push(nxt,head,s+1); } this->pop(); } assert(false); } }QW,QB,QWB,QBW,Qtar; int main(){ cin>>n>>m; tarW={n/2,m/2},tarB={n/2+1,m/2}; W.read(),B.read(); int wdis=QW.bfs(W,tarW); int bdis=QB.bfs(B,tarB); int wbdis=QWB.bfs(W,tarB); int bwdis=QBW.bfs(B,tarW); if(W.type()!=B.type()){ // It means that only white can eat black if(wdis<=bdis){ chooseWhite(); QW.print(); return 0; } if(wbdis<=bdis+1){ chooseWhite(); QWB.print(); if(other.isOnlyOneStepTo(tarB))other.print(); else{ Qtar.bfs(tarB,tarW); Qtar.print(); } return 0; } chooseBlack(); other.read(); QB.print(); } else{ // It means that only black can eat white if(bdis<wdis){ chooseBlack(); other.read(); QB.print(); return 0; } if(bwdis<=wdis){ chooseBlack(); other.read(); QBW.print(); if(other.isOnlyOneStepTo(tarW))other.print(); else{ Qtar.bfs(tarW,tarB); Qtar.print(); } return 0; } chooseWhite(); QW.print(); } return 0; }
- 1
信息
- ID
- 1782
- 时间
- 3000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 2
- 已通过
- 1
- 上传者