Codeforces Beta Round #99 (Div. 1) D : World of Darkraft

問題概要

H*W(H,W<20)のボードがある。各マスにはL,R,Xのいずれかが書かれている。プレイヤーは交互に黒く塗りつぶされていないマスを選ぶ。選んだマスがRのときは、そのマスから左下と右上に向かって、塗りつぶされているマスにぶつかるか端に到達するまでマスを黒く塗りつぶす。Lのときは左上から右下まで。XのときはRとL両方。マスを塗りつぶせなくなった方の負け。どちらが勝つか判定する問題。

解法

基本的には分裂するgrundy数なんだけど、斜めのチョコレート割の扱いに困った。y+xとy-x(+W)の下限と上限を持っておけばうまく処理できる。

acceptされたコード

#include <cstdio>
#include <set>
using namespace std;

const int MAX_N = 20;

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

void init() {
	scanf("%d%d", &H, &W);
	for (int i = 0; i < H; ++i) {
		scanf(" %s ", board[i]);
	}
}

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

int calcGrundy(int plow, int pupper, int mlow, int mupper, int odd) {
	if (visited[plow][pupper][mlow][mupper][odd]) {
		return grundy[plow][pupper][mlow][mupper][odd];
	}
	visited[plow][pupper][mlow][mupper][odd] = true;

	int& ret = grundy[plow][pupper][mlow][mupper][odd] = 0;

	set<int> visibleState;
	for (int y = 0; y < H; ++y) {
		for (int x = 0; x < W; ++x) if ((x+y)%2 == odd) {
			const int plus = y + x, minus = y - x + W;
			if (plow <= plus && plus < pupper && mlow <= minus && minus < mupper) {
				const char cell = board[y][x];
				int xo = 0;
				if (cell == 'L') {
					xo = calcGrundy(plow, plus, mlow, mupper, odd) ^ calcGrundy(plus+1, pupper, mlow, mupper, odd);
				}
				if (cell == 'R') {
					xo = calcGrundy(plow, pupper, mlow, minus, odd) ^ calcGrundy(plow, pupper, minus+1, mupper, odd);
				}
				if (cell == 'X') {
					xo = calcGrundy(plow, plus, mlow, minus, odd)
							^ calcGrundy(plow, plus, minus + 1, mupper, odd)
							^ calcGrundy(plus+1, pupper, mlow, minus, odd)
							^ calcGrundy(plus+1, pupper, minus + 1, mupper, odd);
				}
				visibleState.insert(xo);
			}
		}
	}

	for (;visibleState.find(ret) != visibleState.end(); ++ret) ;
	return ret;
}

bool solve() {
	int ans = calcGrundy(0, H+W, 0, H+W, 0) ^ calcGrundy(0, H+W, 0, H+W, 1);
	return  ans != 0;
}

int main() {
	init();
	puts(solve() ? "WIN" : "LOSE");
	return 0;
}