Problem: Example

Input

2 2
..
..


Output

Second

Solution (in CPP):

Solution:
#include <set>
#include <iostream>
using namespace std;
int memo[21][21][21][21];
int H, W;
string C[20];

int grundy(int b, int l, int t, int r){
  if(memo[b][l][t][r] >= 0) return memo[b][l][t][r];
  set<int> S;
  for(int i = b; i < t; ++i){
    for(int j = l; j < r; ++j){
      if(C[i][j] == 'X') continue;
      int x = grundy(b,l,i,j), y = grundy(b,j+1,i,r), z = grundy(i+1,l,t,j), w = grundy(i+1,j+1,t,r);
      S.insert(x^y^z^w);
    }
  }
  for(int i = 0; i <= H*W; ++i){
    if(not S.count(i)){
      memo[b][l][t][r] = i;
      return i;
    }
  }
  return -1;
}

int main(){
  cin >> H >> W;
  for(int i = 0; i <= H; ++i)
    for(int j = 0; j <= W; ++j)
      for(int k = 0; k <= H; ++k)
        fill(memo[i][j][k],memo[i][j][k]+21,-1);

  for(int i = 0; i < H; ++i) cin >> C[i];
  int ans = grundy(0,0,H,W);
  if(not ans) cout << "Second" << endl;
  else cout << "First" << endl;
  return 0;
}