백준11717 Wall Making Game

작성일 | In

문제 링크

  • http://icpc.me/11717

사용 알고리즘

  • DP
  • Sprague-Grundy

시간복잡도

  • $O(H^3W^3)$

풀이

$D(r1, r2, c1, c2) := (r1, c1)$부터 $(r2, c2)$까지로 구성된 보드의 Grundy Number로 정의하면, $O(H^3W^3)$ 시간에 전체 보드의 Grundy Number를 계산할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define IDX(v, x) (lower_bound(all(v), x) - v.begin())
using namespace std;

using uint = unsigned;
using ll = long long;
using ull = unsigned long long;

int N, M;
int A[22][22], D[22][22][22][22];

int Grundy(int r1, int r2, int c1, int c2){
    if(r1 < 1 || c1 < 1 || r2 > N || c2 > M || r1 > r2 || c1 > c2) return 0;
    int &res = D[r1][r2][c1][c2];
    if(res != -1) return res;
    set<int> st;
    for(int i=r1; i<=r2; i++){
        for(int j=c1; j<=c2; j++){
            if(A[i][j]) continue;
            int now = Grundy(r1, i-1, c1, j-1) ^ Grundy(r1, i-1, j+1, c2) ^ Grundy(i+1, r2, c1, j-1) ^ Grundy(i+1, r2, j+1, c2);
            st.insert(now);
        }
    }
    for(int i=0; ; i++) if(!st.count(i)) return res = i;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M;
    for(int i=1; i<=N; i++){
        for(int j=1; j<=M; j++){
            char c; cin >> c; A[i][j] = c == 'X';
        }
    }
    memset(D, -1, sizeof D);
    if(Grundy(1, N, 1, M)) cout << "First";
    else cout << "Second";
}