Eat the Chip

题目描述

Alice and Bob are playing a game on a checkered board. The board has $h$ rows, numbered from top to bottom, and $w$ columns, numbered from left to right. Both players have a chip each. Initially, Alice’s chip is located at the cell with coordinates $(x_a,y_a)$ (row $x_a$, column $y_a$), and Bob’s chip is located at $(x_b,y_b)$. It is guaranteed that the initial positions of the chips do not coincide. Players take turns making moves, with Alice starting.

On her turn, Alice can move her chip one cell down or one cell down-right or down-left (diagonally). Bob, on the other hand, moves his chip one cell up, up-right, or up-left. It is not allowed to make moves that go beyond the board boundaries.

More formally, if at the beginning of Alice’s turn she is in the cell with coordinates $(x_a,y_a)$, then she can move her chip to one of the cells $(x_a+1,y_a)$, $(x_a+1,y_a-1)$, or $(x_a+1,y_a+1)$. Bob, on his turn, from the cell $(x_b,y_b)$ can move to $(x_b-1,y_b)$, $(x_b-1,y_b-1)$, or $(x_b-1,y_b+1)$. The new chip coordinates $(x^{\prime },y^{\prime })$ must satisfy the conditions $1\le x^{\prime }\le h$ and $1\le y^{\prime }\le w$.

Example game state. Alice plays with the white chip, Bob with the black one. Arrows indicate possible moves.

A player immediately wins if they place their chip in a cell occupied by the other player’s chip. If either player cannot make a move (Alice—if she is in the last row, i.e. $x_a=h$, Bob—if he is in the first row, i.e. $x_b=1$), the game immediately ends in a draw.

What will be the outcome of the game if both opponents play optimally?

输入描述

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1\le t\le 10^4$) — the number of test cases. This is followed by the description of the test cases.

Each test case consists of a single line containing six integers $h$, $w$, $x_a$, $y_a$, $x_b$, $y_b$ ($1\le x_a,x_b\le h\le 10^6$, $1\le y_a,y_b\le w\le 10^9$) — the dimensions of the board and the initial positions of Alice’s and Bob’s chips. It is guaranteed that either $x_a\ne x_b$ or $y_a\ne y_b$.

It is guaranteed that the sum of $h$ over all test cases does not exceed $10^6$.

输出描述

For each test case, output “Alice” if Alice wins, “Bob” if Bob wins, and “Draw” if neither player can secure a victory. You can output each letter in any case (lowercase or uppercase). For example, the strings “bOb”, “bob”, “Bob”, and “BOB” will be accepted as Bob’s victory.

样例 #1

样例输入 #1

12
6 5 2 2 5 3
4 1 2 1 4 1
1 4 1 3 1 1
5 5 1 4 5 2
4 4 1 1 4 4
10 10 1 6 10 8
10 10 2 6 10 7
10 10 9 1 8 1
10 10 8 1 10 2
10 10 1 1 2 1
10 10 1 3 4 1
10 10 3 1 1 1

样例输出 #1

Alice
Bob
Draw
Draw
Draw
Alice
Draw
Draw
Bob
Alice
Alice
Draw

思路

他逃，他追，他插翅难飞。 题意转化一下就是考虑是否有一方可以追杀另一方(白棋走到黑棋位置或者黑棋走到白棋位置)。两个棋子的下法有显而易见的特点：白棋只会往下走，黑棋只会往上走，且在一个回合后，白棋与黑棋的行间距一定发生了 +2 或 -2 的变化。所以，对于初始行间距确定的白黑棋，二者谁追杀谁是确定的：如果初始行间距为奇数，那么只可能是白棋走到黑棋的位置上，白棋追杀黑棋，即Alice追杀Bob；如果初始行间距为偶数，那么只可能是黑棋走到白棋的位置上，黑棋追杀白棋，即Bob追杀Alice。对于逃跑，根据贪心策略，逃亡者朝着水平上追杀者的反方向逃跑，才最有可能逃跑成功(即造成平局)。所以问题转化为了在追杀情况下，供逃亡者逃跑的水平方向上的剩余列数是否足够。如果足够，平局；不足够，追杀者获胜。而在非追杀情况下(即 $x_a>=x_b$ 时)，一定为平局。

代码

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
typedef long long ll;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--)
    {
        int h, w, xa, ya, xb, yb;
        cin >> h >> w >> xa >> ya >> xb >> yb;
        // 由于Alice的棋子只会往下走，Bob的棋子只会往上走，那么如果xa>=xb，则二者不可能走到同一点，必为平局
        if (xa >= xb)
        {
            cout << "Draw\n";
        }
        else
        {
            // 分两种情况：Alice追杀Bob，Bob追杀Alice
            if (!((xb - xa) & 1)) // 行间距为偶数时，Bob追杀Alice
            {
                if (ya == yb) // 不论逃亡者下棋，追杀者永远可以走到与逃亡者同一列上
                    cout << "Bob\n";
                else
                {
                    int cnt = (xb - xa) / 2; // cnt表示至少需要多少的列数供逃亡者逃亡
                    if (ya > yb)
                    {
                        cnt -= ya - yb - 1;
                        if (cnt <= w - ya) // 逃亡方向剩余列数足够，则平局
                            cout << "Draw\n";
                        else
                            cout << "Bob\n";
                    }
                    else
                    {
                        cnt -= yb - ya - 1;
                        if (cnt <= ya - 1) // 逃亡方向剩余列数足够，则平局
                            cout << "Draw\n";
                        else
                            cout << "Bob\n";
                    }
                }
            }
            else // 行间距为奇数时，Alice追杀Bob
            {
                // 由于Alice先手，可以通过先下一步棋使得ya靠近yb的方式将问题转化为逃亡者先手
                if (ya > yb)
                    ya--;
                if (ya < yb)
                    ya++;
                if (ya == yb) // 不论逃亡者下棋，追杀者永远可以走到与逃亡者同一列上
                    cout << "Alice\n";
                else
                {
                    int cnt = (xb - xa) / 2; // cnt表示至少需要多少的列数供逃亡者逃亡
                    if (ya > yb)
                    {
                        cnt -= ya - yb - 1;
                        if (cnt <= yb - 1) // 逃亡方向剩余列数足够，则平局
                            cout << "Draw\n";
                        else
                            cout << "Alice\n";
                    }
                    else
                    {
                        cnt -= yb - ya - 1;
                        if (cnt <= w - yb) // 逃亡方向剩余列数足够，则平局
                            cout << "Draw\n";
                        else
                            cout << "Alice\n";
                    }
                }
            }
        }
    }

    return 0;
}