专栏文章

题解：P14549 [IO 2024 #3] 原始象棋

UUnion_Find
P14549题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@min3y0ph
此快照首次捕获于
2025/12/01 20:10
3 个月前
此快照最后确认于
2025/12/01 20:10
3 个月前
查看原文
众所不周知，这题可以直接分讨冲过去。
赛时花了 11 小时写分讨，最后是下载数据过的。简单讲有以下几类。
  1. 先手一步秒杀。
  2. n=1n=1 或 m=1m=1，此时一定是车，先手秒杀。
  3. n=2n=2 且 m=2m=2。
  4. n=2n=2 或 m=2m=2。
  5. n=3n=3 且 m=3m=3。
  6. n=3n=3 或 m=3m=3。
  7. n=4n=4 且 m=4m=4。
  8. n=4n=4 或 m=4m=4。
  9. 其他情况，直接平局。
前两种直接先手赢，接下来考虑剩下的。注意这里的分类都不包含前面的情况，后文同理，比如后文不会考虑一步秒杀。
一定要注意文中的标粗段。
后文称满足 x+yx+y 为偶数的格子 (x,y)(x,y) 为白格，反之为黑格。

n=2n=2 且 m=2m=2

  • 如果是两个车，那么一定是对角，那么先手走一步一定会被后手吃掉，后手胜。
  • 如果两个象，那么一定是黑白格，平局。
  • 如果是一个车一个象，那么车一定会吃掉象，不论先后手。
接下来不考虑两个象黑白格的情况。

n=2n=2 或 m=2m=2

这里只讨论 n=2n=2，m=2m=2 同理。
  • 如果两个车，一定会二人转，平局。
  • 如果一个车一个象，车可以压住象的所有移动位置，象一定被吃。
  • 如果两个象，相当于在链上走，考虑距离，距离为奇数先手胜，否则后手胜。

特殊情况：两个象且 n=3n=3 或 m=3m=3

这里特殊处理是因为后面我们只会考虑一个车一个象的情况了，其余一定平局，但是这种情况特例。
Case1.png
这里是 (2,1)(2,1) 先手，(2,3)(2,3) 后手，此时先手可以走的位置只有 (1,2)(1,2) 和 (3,2)(3,2)，一定会被后手吃，所以后手胜。
当然，如果先手一步走成这样子，就是先手胜。
接下来只考虑一个车和一个象的情况。显然象吃不掉车，因为车可以直接站在和象颜色不同的格子。

n=3n = 3 且 m=3m = 3

象位于白格

此时车想要吃掉象，只有可能在一开始压住象的所有可能位置。
Case2.png
黄色是象，红色是车，绿色是象可以走到的位置。
只有这时候象走，那么车会吃掉象。我们称可以车卡住象所有可以走到的点的位置为象的死点。
如果象先手，车一定要位于象的死点。而如果车先手，那么就要一步走到象的死点，且不能位于死点。当然，一个象有两个死点，比如上图除了 (3,2)(3,2)，(2,3)(2,3) 也是一个死点。

象位于黑格

这个简单，只要车占住中心象就死了，车必胜。

n=3n = 3 或 m=3m = 3

结论：此时车一定胜。
考虑下面这种走法。
Case3.png
其中蓝色是车的移动编号，橙色是象的移动编号，对应格子颜色含义同上。
这里象先手，车的目的就是走到象的死点，然后吃掉。但是象一步走到 22 号点，于是为了防止象继续向右（这里没有把右边画出来），所以要车也走到 22 号点，此时象只能回到 11 号点，此时车就可以一步走到象的死点 33 号点。而如果象如果不在角落，我们就可以通过不断把象往角落逼的思路，最后吃掉。

n=4n = 4 且 m=4m = 4

这才是最神秘的部分，花了一晚上想，一开始赛时认为只会出现一步杀，结果发现了两步杀，于是认为只会有两步杀，结果又有三步杀。
先有一个结论。
当象位于中间或角落时，一定平局。
这是因为象可以走到的 44 个位置行列均不同，就算车压住两个位置，象自己占了一个位置，还是有一个位置可以走，所以一定平局。
所以此时车的目的时让象不要走到中间或角落去。

一步杀

Case4.png
此时象只会走到绿色格子，而车会压住所有绿色格子，所以车胜。

两步杀

Case5.png
依旧象先手，位于 11 号点的象只能走到 22 号和 33 号点。紫色表示象的死点。
此时会发现车不论如何都可以走到象的两个死点，于是车胜。

三步杀：第一种

Case6.png
此时象只能走到 22 号或 33 号点，而不管象怎么走，巍峨防止其到中间，车必须走到 22 号点，而象就只能回到 11 号点，车再走到 33 号点，就回到了两步杀的情况。

三步杀：第二种

Case7.png
此时象只能往边缘走，车直接走到边上就是两步杀。

三步杀：第三种

Case8.png
同样的，象只能走到 22 号点，车可以一步变成两步杀。

总结

n=4n=4 且 m=4m=4 时，车可以杀象的 55 种情况。
  • 直接站死点。
  • 在对边相邻点。
  • 在同边相邻点。
  • 在中间的相邻点。
  • 在中间相邻点的对角点。
直接判即可。

n=4n=4 或 m=4m=4

这个比较简单，因为不会出现多步杀的情况了，只要判一步杀即可，即站在死点。

其余情况

这时候象就算在边缘至少也有 33 个不同行列的点来选，车一定抓不住。平局。

代码

话说真的有人看吗？？？
这份代码是在赛时基础上，和 Conan15 一起下载数据出来的，几个我们出过问题的 hack 都在上面的图里了，可以自己测一下。
码字很累，如果有打错的或者没有考虑清楚的地方可以找我。
代码好丑，快看不懂了。
CPP
#include <bits/stdc++.h>
using namespace std;
int T;

int n, m, x, y, xx, yy;
char c, cc;

inline void check(int sx, int sy) {
	puts((sx == xx && sy == yy) ? "LOSE" : "DRAW");
}
inline void check(int sx, int sy, int sxx, int syy) {
	if (sx == x && sy == y) puts("DRAW");
	else if (sxx == x && syy == y) puts("DRAW");
	else if (sx == x || sy == y) puts("WIN");
	else if (sxx == x || syy == y) puts("WIN");
	else puts("DRAW");
}
inline void checkk(int sx, int sy) {
	if (sx == x && sy == y) puts("DRAW");
	else if (sx == x || sy == y) puts("WIN");
	else puts("DRAW");
}
inline void check4(int sx, int sy, int sxx, int syy){
	puts((sx == xx && sy == yy) || (sxx == xx && syy == yy) ? "LOSE" : "DRAW");
}
inline void checkk4(int sx, int sy, int sxx, int syy) {
	if (sx == x && sy == y) puts("DRAW");
	else if (sxx == x && syy == y) puts("DRAW");
	else if (sx == x || sy == y) puts("WIN");
	else if (sxx == x || syy == y) puts("WIN");
	else puts("DRAW");
}
inline bool corner(int x, int y){ return (x == 1 && y == 1) || (x == 1 && y == 4) || (x == 4 && y == 1) || (x == 4 && y == 4); }
inline bool checker4(int x, int y, int xx, int yy){
	if (y - x == yy - xx || x + y == xx + yy) return 0;
	if ((x == 1 || x == 4 || y == 1 || y == 4) && abs(xx - x) + abs(yy - y) == 1 && !corner(xx, yy))
		return 1;
	if (xx > 1 && xx < n && yy > 1 && yy < m){
		if ((x == 1 || x == 4 || y == 1 || y == 4) && abs(5 - xx - x) + abs(5 - yy - y) == 1)
			return 1;
	}
	return 0;
}

void solve() {
	scanf("\n %d%d", &n, &m);
	scanf("\n %d%d %c\n %d%d %c", &x, &y, &c, &xx, &yy, &cc);

	if (n == 1 || m == 1) {
		if (c == 'R') puts("WIN");
		else {
			if (cc == 'R') puts("LOSE");
			else puts("DRAW");
		}
		return;
	}
	if (c == 'R') {
		if (x == xx || y == yy) return puts("WIN"), void();
	} else {
		if (y - x == yy - xx || x + y == xx + yy) return puts("WIN"), void();
	}
	// can't meet
	if (c == 'B' && cc == 'B' && ((x + y) & 1) != ((xx + yy) & 1)) return puts("DRAW"), void();

	if (n == 2 || m == 2) {
		if (c == 'R' && cc == 'B') return puts("WIN"), void();
		else if (c == 'B' && cc == 'R') return puts("LOSE"), void();
		else if (c == 'B' && cc == 'B') {
			if (((x + y) & 1) ^ ((xx + yy) & 1)) return puts("DRAW"), void();
			int dis = abs(x - xx);
			return puts((dis & 1) ? "WIN" : "LOSE"), void();
		} else if (c == 'R' && cc == 'R') {
			if (n == 2 && m == 2) return puts("LOSE"), void();
			return puts("DRAW"), void();
		}
	}
	if (c == 'B' && cc == 'B') {
		if (n == 3 && x == 2 && xx == 2 && ((y == 1 && yy == 3) || (y == m && yy == m - 2))) return puts("LOSE"), void();
		if (m == 3 && y == 2 && yy == 2 && ((x == 1 && xx == 3) || (x == n && xx == n - 2))) return puts("LOSE"), void();
		if (n == 3 && (x == 1 || x == 3) && y == 4  && xx == 2 && yy == 1) return puts("WIN"), void();
		if (n == 3 && (x == 1 || x == 3) && y == m - 3 && xx == 2 && yy == m) return puts("WIN"), void();
		if (m == 3 && (y == 1 || y == 3) && x == 4  && yy == 2 && xx == 1) return puts("WIN"), void();
		if (m == 3 && (y == 1 || y == 3) && x == n - 3 && yy == 2 && xx == n) return puts("WIN"), void();
	}
	if (c == cc) return puts("DRAW"), void();
	if (n == 3 && m == 3){
		if (c == 'B'){
			if (x == 2 && y == 2) return puts("DRAW"), void();
			if (x == 1 && y == 1 && xx == 3 && yy == 2) return puts("LOSE"), void();
			if (x == 1 && y == 3 && xx == 3 && yy == 2) return puts("LOSE"), void();
			if (x == 3 && y == 1 && xx == 1 && yy == 2) return puts("LOSE"), void();
			if (x == 3 && y == 3 && xx == 1 && yy == 2) return puts("LOSE"), void();
			if (x == 1 && y == 1 && xx == 2 && yy == 3) return puts("LOSE"), void();
			if (x == 1 && y == 3 && xx == 2 && yy == 1) return puts("LOSE"), void();
			if (x == 3 && y == 1 && xx == 2 && yy == 3) return puts("LOSE"), void();
			if (x == 3 && y == 3 && xx == 2 && yy == 1) return puts("LOSE"), void();
			if ((x + y) & 1) return puts("LOSE"), void();
			return puts("DRAW"), void();
		} else {
			if (xx == 2 && yy == 2) return puts("DRAW"), void();
			if (xx == 1 && yy == 1) return check(3, 2, 2, 3), void();
			if (xx == 1 && yy == 3) return check(3, 2, 2, 1), void();
			if (xx == 3 && yy == 1) return check(1, 2, 2, 3), void();
			if (xx == 3 && yy == 3) return check(1, 2, 2, 1), void();
			if ((xx + yy) & 1) return puts("WIN"), void();
			return puts("DRAW"), void();
		}
	}
	if (n == 3 || m == 3) {
		if (c == 'B') puts("LOSE");
		else puts("WIN");
		return ;
	}
	if (n == 4 && m == 4){
		if (c == 'B') {
			if (x > 1 && x < n && y > 1 && y < m) return puts("DRAW"), void();
			if (corner(x, y)) return puts("DRAW"), void();
			if (checker4(x, y, xx, yy)) return puts("LOSE"), void();
			if (x == 1 && y == 2) return check4(2, 4, 4, 3), void();
			if (x == 1 && y == 3) return check4(2, 1, 4, 2), void();
			if (x == 2 && y == 1) return check4(4, 2, 3, 4), void();
			if (x == 2 && y == 4) return check4(4, 3, 3, 1), void();
			if (x == 3 && y == 1) return check4(1, 2, 2, 4), void();
			if (x == 3 && y == 4) return check4(1, 3, 2, 1), void();
			if (x == 4 && y == 2) return check4(3, 4, 1, 3), void();
			if (x == 4 && y == 3) return check4(3, 1, 1, 2), void();
		} else {
			if (xx > 1 && xx < n && yy > 1 && yy < m) return puts("DRAW"), void();
			if (corner(xx, yy)) return puts("DRAW"), void();
			for (int i = 1; i <= 4; i++) if (i != x && checker4(xx, yy, i, y))
				return puts("WIN"), void();
			for (int i = 1; i <= 4; i++) if (i != y && checker4(xx, yy, x, i))
				return puts("WIN"), void();
			if (xx == 1 && yy == 2) return checkk4(2, 4, 4, 3), void();
			if (xx == 1 && yy == 3) return checkk4(2, 1, 4, 2), void();
			if (xx == 2 && yy == 1) return checkk4(4, 2, 3, 4), void();
			if (xx == 2 && yy == 4) return checkk4(4, 3, 3, 1), void();
			if (xx == 3 && yy == 1) return checkk4(1, 2, 2, 4), void();
			if (xx == 3 && yy == 4) return checkk4(1, 3, 2, 1), void();
			if (xx == 4 && yy == 2) return checkk4(3, 4, 1, 3), void();
			if (xx == 4 && yy == 3) return checkk4(3, 1, 1, 2), void();
		}
	}
	if (n == 4 || m == 4){
		if (c == 'B') {
			if (x > 1 && x < n && y > 1 && y < m) return puts("DRAW"), void();
			if ((x == 1 || x == n) && (m > 4 || y == 1 || y == m)) return puts("DRAW"), void();
			if ((y == 1 || y == m) && (n > 4 || x == 1 || x == n)) return puts("DRAW"), void();
			if (x == 1 && y == 2 && m == 4) return check(2, 4), void();
			if (x == 1 && y == 3 && m == 4) return check(2, 1), void();
			if (x == 2 && y == 1 && n == 4) return check(4, 2), void();
			if (x == 2 && y == m && n == 4) return check(4, m - 1), void();
			if (x == 3 && y == 1 && n == 4) return check(1, 2), void();
			if (x == 3 && y == m && n == 4) return check(1, m - 1), void();
			if (x == n && y == 2 && m == 4) return check(n - 1, 4), void();
			if (x == n && y == 3 && m == 4) return check(n - 1, 1), void();
		} else {
			if (xx > 1 && xx < n && yy > 1 && yy < m) return puts("DRAW"), void();
			if ((xx == 1 || xx == n) && (m > 4 || yy == 1 || yy == m)) return puts("DRAW"), void();
			if ((yy == 1 || yy == m) && (n > 4 || xx == 1 || xx == n)) return puts("DRAW"), void();
			if (xx == 1 && yy == 2 && m == 4) return checkk(2, 4), void();
			if (xx == 1 && yy == 3 && m == 4) return checkk(2, 1), void();
			if (xx == 2 && yy == 1 && n == 4) return checkk(4, 2), void();
			if (xx == 2 && yy == m && n == 4) return checkk(4, m - 1), void();
			if (xx == 3 && yy == 1 && n == 4) return checkk(1, 2), void();
			if (xx == 3 && yy == m && n == 4) return checkk(1, m - 1), void();
			if (xx == n && yy == 2 && m == 4) return checkk(n - 1, 4), void();
			if (xx == n && yy == 3 && m == 4) return checkk(n - 1, 1), void();
		}
	}
	puts("DRAW");
}

int main() {
	scanf("%d", &T);
	while (T--) solve();
	return 0;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...