Description

一个 \(n \times n (n \leq 2)\) 棋盘上有黑白棋子各一枚. 游戏者 A 和 B 轮流移动棋子, A 先走.

  • A 的移动规则: 只能移动白棋子. 可以往上下左右四个方向之一移动一格.
  • B 的移动规则: 只能移动黑棋子. 可以往上下左右四个方向之一移动一格或者两格.

和通常的 “吃子” 规则一样, 当某游戏者把自己的棋子移动到对方棋子所在的格子时, 他就 赢了. 两个游戏者都很聪明, 当可以获胜时会尽快获胜, 只能输掉的时候会尽量拖延时间. 你的任务是判断谁会赢, 需要多少回合.

比如 \(n=2\), 白棋子在 \((1,1)\), 黑棋子在 \((2,2)\), 那么虽然 A 有两种走法, 第二个回合 B 总能取胜.

Input

输入仅一行, 包含五个整数 \(n, r_1, c_1, r_2, c_2\), 即棋盘大小和棋子位置. 白色棋子 在 \((r_1,c_1)\), 黑色棋子在 \((r_2,c_2)\). 黑白棋子的位置保证不相同.

Output

输出仅一行, 即游戏结果. 如果 A 获胜, 输出 WHITE x; 如果 B 获胜, 输出 BLACK x; 如果二者都没有必胜策略, 输出 DRAW.

Sample Input

2 1 1 2 2

Sample Output

BLACK 2

Data Range

对于 100% 的数据, 保证 \(1 \leq r_1, c_1, r_2, c_2 \leq n \leq 20\)

Explanation

大家是不是觉得 A 很惨......

首先当两个人开始杠的时候 (就是面对面), B 肯定占优势. 因为如果 A 要往一个方向挪的 时候, B 肯定可以把他挡住, 然后还可以从旁边绕过去. 但是如果 A 可以堵住他的话 (不然 B 就一定赢了), A 肯定会想方设法让游戏无限玩下去

如果 A 挡不住 B, 则 B 跑的比谁都快, 然后马上就可以窜到 A 的大本营里

综上总是不会出现平局~

然后由于 A 比较弱, 所以只有在 A 离 B 一格时 (B 先走, 然后把自己的地方让开, A 见缝插针 赢掉这场比赛), A 才有可能赢, 不然总是 B.

然后记忆化暴力搜索一下就可以了.

话说为什么我把这道题一本正经地交到 3107 的位置上去了还 WA 了两次 233~

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;
const int maxn = 22;
const int infinit = 0x003f3f3f;

int n, x1, y1, x2, y2;
int dp_arr[2][3 * maxn][maxn][maxn][maxn][maxn];

#define maximize(__x,__y) __x=max(__x,__y)
#define minimize(__x,__y) __x=min(__x,__y)
#define maximize_res(__y) maximize(res,__y)
#define minimize_res(__y) minimize(res,__y)
int dfs(int x, int y, int a, int b, int c, int d)
{
    // Too long a distance went, impossible to be determined
    if (y > 3 * n)
        return infinit;
    // Successive reach / Duplication
    if (a == c && b == d) {
        if (x == 1) // White has reached the target, an infinite loop
            return infinit;
        return 0;
    }
    // Lazy evaluation tricks
    if (dp_arr[x][y][a][b][c][d])
        return dp_arr[x][y][a][b][c][d];
    // About to check on the states
    int res = 0;
    if (x == 0) {
        res = 0; // Finding maximum depth
        if (a > 1)     maximize_res( dfs(1, y + 1, a - 1, b, c, d) );
        if (a < n)     maximize_res( dfs(1, y + 1, a + 1, b, c, d) );
        if (b > 1)     maximize_res( dfs(1, y + 1, a, b - 1, c, d) );
        if (b < n)     maximize_res( dfs(1, y + 1, a, b + 1, c, d) ); // This could have been '>'
    } else if (x == 1) {
        res = infinit; // Finding minimum depth
        if (c > 1)     minimize_res( dfs(0, y + 1, a, b, c - 1, d) );
        if (c > 2)     minimize_res( dfs(0, y + 1, a, b, c - 2, d) );
        if (c < n)     minimize_res( dfs(0, y + 1, a, b, c + 1, d) );
        if (c < n - 1) minimize_res( dfs(0, y + 1, a, b, c + 2, d) );
        if (d > 1)     minimize_res( dfs(0, y + 1, a, b, c, d - 1) );
        if (d > 2)     minimize_res( dfs(0, y + 1, a, b, c, d - 2) );
        if (d < n)     minimize_res( dfs(0, y + 1, a, b, c, d + 1) );
        if (d < n - 1) minimize_res( dfs(0, y + 1, a, b, c, d + 2) );
    }
    // Needs a depth update
    res++;
    dp_arr[x][y][a][b][c][d] = res;
    return res;
}

int main(int argc, char** argv)
{
    scanf("%d%d%d%d%d", &n, &x1, &y1, &x2, &y2);
    // That is sufficient for a white node to achieve target
    if (abs(x2 - x1) + abs(y2 - y1) <= 1)
        printf("WHITE 1\n");
    else
        printf("BLACK %d\n", dfs(0, 0, x1, y1, x2, y2));
    return 0;
}