Codeforces 138D World of Darkraft 题解《挑战程序设计竞赛》-码农场

4.2找出游戏的必胜策略
Nim与Grundy数

挑战程序设计竞赛第二版.jpg

暗黑世界：H*W的棋盘中每个点都是L、R、X三者之一，两人轮流选一个点，若为L则向左下和右上发射激光，R向右下和左上发射，X则相当于LR的组合——同时向四个方向发射。激光所至的点会被摧毁，只有已摧毁的点或棋盘边界才会挡住激光。若在某回合开始时所有点都被摧毁，则该人失败。问先手是否有必胜策略？

4.2找出游戏的必胜策略

Nim与Grundy数

由于激光的方向，所以首先将棋盘染成国际象棋棋盘的黑白两色：

国际象棋.png

这样将整个游戏一分为二，只有颜色相同的点才属于同一个子游戏。

接下来按照激光射线分割子游戏，在《POJ 3537 Crosses and Crosses》中，纸条是一维的，一刀两断，可以很方便地拆分为两个子游戏的组合。但在这里，棋盘是二维的，每次操作可能分为两部分或四部分。

另外，激光的方向是与坐标轴成45°的，为了方便处理，将棋盘顺时针旋转45°。坐标(x,y)被映射为(x+y, x-y+W)，于是射线分割的结果就是矩形而不是三角形或不规则的多边形了。

#include <iostream>
#include <cstring>
using namespace std;

#define MAX_N 20

int H, W;
char board[MAX_N + 1][MAX_N + 1];

int grundy[2 * MAX_N + 1][2 * MAX_N + 1][2 * MAX_N + 1][2 * MAX_N + 1][2];

int search(int x_min, int x_max, int y_min, int y_max, int odd)
{
    int &ret = grundy[x_min][x_max][y_min][y_max][odd];
    if (ret != -1) return ret;

    char s[MAX_N *2 + 1] = {0};
    for (int y = 0; y < H; ++y)
    {
        for (int x = 0; x < W; ++x)
        {
            if (((x + y) & 1) == odd)
            {
                const int x_ = y + x, y_ = y - x + W;
                if (x_min <= x_ && x_ < x_max && y_min <= y_ && y_ < y_max)
                {
                    const char cell = board[y][x];
                    int g = 0;
                    if (cell == 'L')
                    {// 垂直于X轴一分为二
                        g = search(x_min, x_, y_min, y_max, odd) ^ search(x_ + 1, x_max, y_min, y_max, odd);
                    }
                    if (cell == 'R')
                    {// 垂直于Y轴一分为二
                        g = search(x_min, x_max, y_min, y_, odd) ^ search(x_min, x_max, y_ + 1, y_max, odd);
                    }
                    if (cell == 'X')
                    {// 垂直于XY轴分为四部分
                        g = search(x_min, x_, y_min, y_, odd) ^ search(x_min, x_, y_ + 1, y_max, odd) ^
                             search(x_ + 1, x_max, y_min, y_, odd) ^
                             search(x_ + 1, x_max, y_ + 1, y_max, odd);
                    }
                    s[g] = 1;
                }
            }
        }
    }

    while (s[++ret]);
    return ret;
}

int main()
{
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#endif
    scanf("%d%d", &H, &W);
    for (int i = 0; i < H; ++i)
    {
        scanf(" %s ", board[i]);
    }
    memset(grundy, -1, sizeof(grundy));

    puts(search(0, H + W, 0, H + W, 0) ^ search(0, H + W, 0, H + W, 1) ? "WIN" : "LOSE");
#ifdef LOCAL
    fclose(stdin);
#endif
    return 0;
}