CF1201E2 - Knightmare (hard)

Posted on Edited on In

CF1201E2 - Knightmare (hard)

题目大意

\(n\times m(2|n,2|m)\) 的棋盘上有两个 马 (Knight是国际象棋) 分别位于 \(S_1=(x_1,y_1),S_2=(x_2,y_2)\)

他们分别要到达 \(T_1=(\frac{n}{2},\frac{m}{2}),T_2=(\frac{n}{2}+1,\frac{m}{2})\)

一方胜利的情况是：

1.吃掉另一方

2.到达自己的目标位置，且这个位置不能被另一方吃掉

你可以选定操作先手还是后手，要求和交互器交互，并且在350步内取胜


分析

首先是一个重要的性质：双方必然有一方永远无法吃掉另一方

考虑象棋的移动，每次 \((x\pm 1,y\pm 2)\) 或者 \((x\pm 2,y\pm 1)\)

每次操作，必然导致 \(x+y\mod 2\) 改变，在双方轮流操作的过程中

必然有一方走的时候永远无法和另一方同奇偶，也就是无法吃掉另一方


在此基础上，考虑几种情况

设 \(D(a,b)\) 为 \(a,b\) 两点的距离， \(f\) 为先手是否永远不会被吃

1.先手可以在不被后手吃掉的情况下到达目标，且先于后手

先于后手即 \(D(S_1,T_1)\leq D(S_2,T_2)\)

先手不被后手吃掉的情况

  1. \(f\) ： 显然

  2. \(D(S_1,T_1)<D(S_2,T_1)\) ：

此时，假设后手存在一个吃掉先手的策略

那么后手经过这个吃掉先手的点到达 \(T_1\) 的最短路一定和先手相同，故矛盾


2.后手可以在不被先手吃掉的情况下到达目标，且先于先手

\(D(S_1,T_1)>D(S_2,T_2)\)

对称情况

  1. \(not\ f\)

  2. \(D(S_2,T_2)<D(S_1,T_2)-1\)

以上两种情况均直接冲最短路到达目标


3.双方均无法安全直接抵达目标

此时，考虑选择不会被吃的一方操作

由于自己是无敌的，可以考虑先猛扑对方的终点

3.1 \(f=true\) ，选择先手

先走到 \(T_2\) 堵住后手，然后可以绕三步到达 \(T_1\)

先手占据 \(T_2\) 时，后手无法到达 \(T_2\)

走第一步时，由于先手限制着，后手无法进入 \(T_2\)

走第二步时，根据奇偶性分析，后手无法到达 \(T_2\) 的奇偶性

第三步到达目标

3.2 \(f=false\) ，同理

实现

可以好好封装一下

我曾经以为不用读入

由于交互器下面读入的参数可能会让交互器走智障操作

如果能吃掉对方，一定要直接吃掉

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
const int N=1010,INF=1e9+10;
const int dx[]={1,1,-1,-1,2,2,-2,-2};
const int dy[]={2,-2,2,-2,1,-1,1,-1};

int n,m,opt;
int x=-2,y=-2;
void input(){ 
	x=rd(),y=rd(); 
	if(x==-1) exit(0);
}
void CB(){ puts("BLACK"),fflush(stdout),input(); }
void CW(){ puts("WHITE"),fflush(stdout); }

struct Bfser{
	int dis[N][N],pre[N][N];
	int QX[N*N],QY[N*N],L,R;
	int u,v;
	int Reach() {
		int a=abs(u-x),b=abs(y-v);
		if(a>b) swap(a,b);
		return a==1 && b==2;
	}
	void Bfs(int x,int y){
		u=x,v=y;
		QX[L=R=1]=x,QY[1]=y,pre[x][y]=-1,dis[x][y]=1;
		for(;L<=R;) {
			x=QX[L],y=QY[L++];
			rep(i,0,7) {
				int x1=x+dx[i],y1=y+dy[i];
				if(x1<1 || y1<1 || x1>n || y1>m || dis[x1][y1]) continue;
				dis[x1][y1]=dis[x][y]+1,QX[++R]=x1,QY[R]=y1,pre[x1][y1]=i;
			}
		}
	}
	void Go(int d,int k=1) {
		if(Reach()) printf("%d %d\n",x,y),fflush(stdout),exit(0);
		printf("%d %d\n",u+=dx[d],v+=dy[d]),fflush(stdout);
		if(k) input();
	}
	void Go(int x,int y,int k) {
		vector <int> s;
		while(~pre[x][y]) {
			int t=pre[x][y];
			s.pb(t),x-=dx[t],y-=dy[t];
		}
		drep(i,s.size()-1,0) Go(s[i],k+i);
	}
} B,W;

int main(){
	n=rd(),m=rd();
	int x1=rd(),y1=rd(),x2=rd(),y2=rd();
	W.Bfs(x1,y1),B.Bfs(x2,y2);
	int f=((x1+y1)&1)!=((x2+y2)&1);
	if(W.dis[n/2][m/2]<=B.dis[n/2+1][m/2] && (f || W.dis[n/2][m/2]<B.dis[n/2][m/2])) {
		CW(),x=x2,y=y2,W.Go(n/2,m/2,0);
	} else if(B.dis[n/2+1][m/2]<W.dis[n/2][m/2] && (B.dis[n/2+1][m/2]<W.dis[n/2+1][m/2]-1 || !f)) {
		CB(),B.Go(n/2+1,m/2,0);
	} else if(f) {
		CW(),x=x2,y=y2,W.Go(n/2+1,m/2,1);
		W.Go(2),W.Go(5),W.Go(7,0);
	} else {
		CB(),B.Go(n/2,m/2,1);
		B.Go(0),B.Go(7),B.Go(5,0);
	}
}