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

Union_Find · 2025-11-20 21:30:05 · 题解

~~众所不周知，这题可以直接分讨冲过去。~~

赛时花了 1 小时写分讨，最后是下载数据过的。简单讲有以下几类。

先手一步秒杀。
其他情况，直接平局。

前两种直接先手赢，接下来考虑剩下的。注意这里的分类都不包含前面的情况，后文同理，比如后文不会考虑一步秒杀。

一定要注意文中的标粗段。

后文称满足 x+y 为偶数的格子 (x,y) 为白格，反之为黑格。

n=2 且 m=2

如果是两个车，那么一定是对角，那么先手走一步一定会被后手吃掉，后手胜。
如果两个象，那么一定是黑白格，平局。
如果是一个车一个象，那么车一定会吃掉象，不论先后手。

接下来不考虑两个象黑白格的情况。

n=2 或 m=2

这里只讨论 n=2，m=2 同理。

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

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

这里特殊处理是因为后面我们只会考虑一个车一个象的情况了，其余一定平局，但是这种情况特例。

这里是 (2,1) 先手，(2,3) 后手，此时先手可以走的位置只有 (1,2) 和 (3,2)，一定会被后手吃，所以后手胜。

当然，如果先手一步走成这样子，就是先手胜。

接下来只考虑一个车和一个象的情况。显然象吃不掉车，因为车可以直接站在和象颜色不同的格子。

n = 3 且 m = 3

象位于白格

此时车想要吃掉象，只有可能在一开始压住象的所有可能位置。

黄色是象，红色是车，绿色是象可以走到的位置。

只有这时候象走，那么车会吃掉象。我们称可以车卡住象所有可以走到的点的位置为象的死点。

如果象先手，车一定要位于象的死点。而如果车先手，那么就要一步走到象的死点，且不能位于死点。当然，一个象有两个死点，比如上图除了 (3,2)，(2,3) 也是一个死点。

象位于黑格

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

n = 3 或 m = 3

结论：此时车一定胜。

考虑下面这种走法。

其中蓝色是车的移动编号，橙色是象的移动编号，对应格子颜色含义同上。

这里象先手，车的目的就是走到象的死点，然后吃掉。但是象一步走到 2 号点，于是为了防止象继续向右（这里没有把右边画出来），所以要车也走到 2 号点，此时象只能回到 1 号点，此时车就可以一步走到象的死点 3 号点。而如果象如果不在角落，我们就可以通过不断把象往角落逼的思路，最后吃掉。

n = 4 且 m = 4

这才是最神秘的部分，花了一晚上想，一开始赛时认为只会出现一步杀，结果发现了两步杀，于是认为只会有两步杀，结果又有三步杀。

先有一个结论。

当象位于中间或角落时，一定平局。

这是因为象可以走到的 4 个位置行列均不同，就算车压住两个位置，象自己占了一个位置，还是有一个位置可以走，所以一定平局。

所以此时车的目的时让象不要走到中间或角落去。

一步杀

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

两步杀

依旧象先手，位于 1 号点的象只能走到 2 号和 3 号点。紫色表示象的死点。

此时会发现车不论如何都可以走到象的两个死点，于是车胜。

三步杀：第一种

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

三步杀：第二种

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

三步杀：第三种

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

总结

- 直接站死点。 - 在对边相邻点。 - 在同边相邻点。 - 在中间的相邻点。 - 在中间相邻点的对角点。直接判即可。 ## $n=4$ 或 $m=4

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

其余情况

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

代码

~~话说真的有人看吗？？？~~

这份代码是在赛时基础上，和 Conan15 一起下载数据出来的，几个我们出过问题的 hack 都在上面的图里了，可以自己测一下。

码字很累，如果有打错的或者没有考虑清楚的地方可以找我。

~~代码好丑，快看不懂了。~~

#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;
}