CF1921E 题解

yyrwlj · 2024-01-16 15:32:54 · 题解

题意简述

爱丽丝和鲍勃在一个 n \times m 的棋盘上下棋，两人各有一枚棋子在棋盘上。

两人由爱丽丝开始轮流行动，爱丽丝每次行动能将自己的棋子向左下、正下或右下移动，鲍勃每次行动能将自己的棋子向左上、正上或右上移动。注意不能将棋子移出棋盘外。

当有玩家将自己的棋子移到对方棋子的位置上时，该玩家获胜。若有玩家无法移动自己的棋子，那么游戏立即以平局结束。

两人都绝顶聪明，求出谁会获胜或告知平局。

思路

不妨设最开始两人的棋子都在同一列上，很显然若棋子行坐标之差为偶数，则先手必败。

证明：首先爱丽丝移到哪一列，鲍勃都可以跟上，最后行坐标之差为 2 时，爱丽丝移动后，鲍勃就可以移动到爱丽丝的位置上了。

那么再推广到不同列，因为两人绝顶聪明，所以知道自己若在同一列必然会输的一方，肯定会尽可能地躲避另一方，追求平局。在同一列必然会赢的一方也肯定会尽量追。

我们发现，能不能追到无路可躲（到棋盘边缘）的时候不是那么好求。

但是行数最多只有 10^6，所以循环模拟即可。

具体实现时会有很多细节需要注意，接下来看代码。

Code

#include <iostream>
using namespace std;
void work()
{
    int n, m, xa, ya, xb, yb;
    scanf("%d%d%d%d%d%d", &n, &m, &xa, &ya, &xb, &yb);
    if (xa > xb) //如果鲍勃已经在爱丽丝上方，那就肯定平局。
    {
        puts("Draw");
        return;
    }
    int xc = xb - xa;
    if (ya == yb)
    {
        if (xc & 1)
            puts("Alice");
        else
            puts("Bob");
        return;
    }
    if (xc & 1) // 爱丽丝追鲍勃
    {
        while (xa < xb)
        {
            if (yb < ya) // 往鲍勃的方向追
                ya --;
            else if (yb > ya)
                ya ++;
            else        // 如果已经在同一列
            {
                puts("Alice");
                return;
            }
            xa ++;
            if (xa == xb && ya == yb)
            {
                puts("Alice");
                return;
            }
            if (yb < ya && yb > 1) // 往反方向躲
                yb --;
            else if (yb > ya && yb < m)
                yb ++;
            xb --;
            if (xa == xb && ya == yb)
            {
                puts("Alice");
                return;
            }
        }
        puts("Draw");
    }
    else    // 爱丽丝躲鲍勃
    {
        while (xa < xb)
        {
            if (yb < ya)
            {
                if (ya < m)
                    ya ++;
            }
            else if (ya < yb)
            {
                if (1 < ya)
                    ya --;
            }
            else
            {
                if (xb - xa <= 1)
                    puts("Draw");
                else
                    puts("Bob");
                return;
            }
            xa ++;
            if (xa == xb && ya == yb)
            {
                puts("Bob");
                return;
            }
            if (yb < ya)
                yb ++;
            else
                yb --;
            xb --;
            if (xa == xb && ya == yb)
            {
                puts("Bob");
                return;
            }
        }
        puts("Draw");
    }
}
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
        work();
    return 0;
}