Problem: Example

Input

2 2
..
..


Output

Second

Solution (in CPP):

Solution:
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
int h,w;
int memo[21][21][21][21];//semiopen
bool mark[20][20];
void init(){
    REP(ys,21) REP(yt,21) REP(xs,21) REP(xt,21){
        if(ys>yt || xs>xt) memo[ys][yt][xs][xt] = 0;
        else memo[ys][yt][xs][xt] = -1;
    }
    memset(mark, 0, sizeof(mark));
}

int grundy(int ys, int yt, int xs, int xt){
    if(memo[ys][yt][xs][xt] != -1){
        return memo[ys][yt][xs][xt];
    }
    vector<int> trans;
    for(int i=ys; i<yt; i++){
        for(int j=xs; j<xt; j++){
            if(mark[i][j]) continue;
            int gn = 0;
            gn ^= grundy(ys, i, xs, j);
            gn ^= grundy(i+1, yt, xs, j);
            gn ^= grundy(ys, i, j+1, xt);
            gn ^= grundy(i+1, yt, j+1, xt);
            trans.push_back(gn);
        }
    }
    sort(trans.begin(), trans.end());
    trans.erase(unique(trans.begin(), trans.end()), trans.end());
    int res = 0;
    for(int i=0; i<(int)trans.size(); i++){
        if(trans[i] != i) break;
        res++;
    }
    memo[ys][yt][xs][xt] = res;
    return res;
}

int main(){
    init();
    cin >> h >> w;
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            char c;
            cin >> c;
            if(c == 'X') mark[i][j] = true;
        }
    }
    if(grundy(0, h, 0, w) != 0){
        cout << "First" << endl;
    }else{
        cout << "Second" << endl;
    }
    return 0;
}