Problem: Example

Input

2 2
..
..


Output

Second

Solution (in CPP):

Solution:
#include <bits/stdc++.h>

using namespace std;

const int vy[] = {-1, 1, 0, 0}, vx[] = {0, 0, -1, 1};

int H, W;
string S[20];
int dp[20][20][21][21];

int rec(int sx, int sy, int gx, int gy)
{
  if(sx >= gx || sy >= gy) return (0);
  if(~dp[sx][sy][gx][gy]) return (dp[sx][sy][gx][gy]);
  set< int > grundy;
  for(int mx = sx; mx < gx; mx++) {
    for(int my = sy; my < gy; my++) {
      if(S[my][mx] == 'X') continue;
      grundy.insert(rec(sx, sy, mx, my) ^
                    rec(mx + 1, sy, gx, my) ^
                    rec(sx, my + 1, mx, gy) ^
                    rec(mx + 1, my + 1, gx, gy));
    }
  }
  int ret = 0;
  while(grundy.count(ret)) ++ret;
  return (dp[sx][sy][gx][gy] = ret);
}

int main()
{
  cin >> H >> W;
  for(int i = 0; i < H; i++) {
    cin >> S[i];
  }
  memset(dp, -1, sizeof(dp));
  if(rec(0, 0, W, H)) cout << "First" << endl;
  else cout << "Second" << endl;
}