Problem: Example

Input

2 2
..
..


Output

Second

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;

bool G[21][21];
int dp[21][21][21][21];

int h, w;

int grundy(int si, int sj, int gi, int gj){
    int &res = dp[si][sj][gi][gj];
    if(res != -1) return res;

    res = 0;
    if(si > gi || sj > gj) return res;

    vector<int> result;

    for(int i = si; i < gi; i++){
        for(int j = sj; j < gj; j++){
            if(G[i][j]) continue;
            int g = 0;
            g ^= grundy(si, sj, i, j);
            g ^= grundy(si, j + 1, i, gj);
            g ^= grundy(i + 1, sj, gi, j);
            g ^= grundy(i + 1, j + 1, gi, gj);
            result.push_back(g);
        }
    }

    /*sif(si == 0 && sj == 0 && gi == h && gj == w){
        cout << "hoge~~~~" << endl;
        for(int i = 0; i < (int)result.size(); i++){
            cout << result[i] << " ";
        }
        cout << endl;
    }*/
    sort(result.begin(), result.end());
    result.erase(unique(result.begin(), result.end()), result.end());
    

    for(int i = 0; i < (int)result.size(); i++){
        if(result[i] != i) break;
        res++;
    }

    //cout << "[" << si << "][" << sj << "][" << gi << "][" << gj << "] = " << res << endl;
    return res;
}

int main(){

    memset(dp, -1, sizeof(dp));
    cin >> h >> w;
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            char in; cin >> in;
            G[i][j] = (in == 'X');
        }
    }

    if(grundy(0, 0, h, w) == 0) cout << "Second" << endl;
    else cout << "First" << endl;
    return 0;

}