[백준 11717] Wall Making Game [Platinum II]

https://www.acmicpc.net/problem/11717

11717번: Wall Making Game

 

 다각형 게임과 비슷하게, 행동을 하나 하면 게임판이 여러 개로 나뉘는 문제기 때문에 스프라그-그런디 정리로 문제를 해결할 수 있다. 게임판이 하나 있다면 그 게임판에 대한 그런디 수를

• 게임판 내의 모든 칸에 대해서
• 하나의 칸을 골라 행동을 했다고 가정하고 그때 생기는 4개의 게임판에 대해 재귀적으로 그런디 넘버를 구한 뒤
• 4개의 수를 모두 xor해 주면 행동 하나에 대한 그런디 넘버가 생긴다. 이를 hash set에 푸시.
• 마지막으로 그 set의 mex를 구해서 최종적으로 그런디 넘버를 결정한다.

 게임판은 모두 직사각형 모양이므로 왼쪽 위, 왼쪽 아래, 오른쪽 위, 오른쪽 아래 4개의 수만 저장하면 게임판 하나의 정보를 저장할 수 있다. 따라서 4차원 dp를 돌려 문제를 풀 수 있다. 시간복잡도는 O(S^3) where S = MN.

#include <bits/stdc++.h>

void solve() {
    int I, J;
    std::cin >> I >> J;
    
    std::vector<std::string> board(I);
    for (auto &s : board) {
        std::cin >> s;
    }
    
    auto memo =
            std::vector(I, std::vector(I, std::vector(J, std::vector(J, -1))));
    std::function<int(int, int, int, int)> dp;
    dp = [&](int il, int ir, int jl, int jr) -> int {
        if (il < 0 or il >= I or ir < 0 or ir >= I) {
            return 0;
        }
        if (jl < 0 or jl >= J or jr < 0 or jr >= J) {
            return 0;
        }
        if (memo[il][ir][jl][jr] != -1) {
            return memo[il][ir][jl][jr];
        }

        std::unordered_set<int> us;
        for (int i = il; i <= ir; ++i) {
            for (int j = jl; j <= jr; ++j) {
                if (board[i][j] == '.') {
                    int ret = 0;
                    ret ^= dp(il, i - 1, jl, j - 1);
                    ret ^= dp(i + 1, ir, jl, j - 1);
                    ret ^= dp(il, i - 1, j + 1, jr);
                    ret ^= dp(i + 1, ir, j + 1, jr);
                    us.insert(ret);
                }
            }
        }
        
        for (int i = 0;; ++i) {
            if (us.find(i) == us.end()) {
                return memo[il][ir][jl][jr] = i;
            }
        }
    };
    
    std::cout << (dp(0, I - 1, 0, J - 1) == 0 ? "Second\n" : "First\n");
}

#ifndef LOCAL
int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    solve();
}
#endif