Problem: Example

Input

2 2
..
..


Output

Second

Solution (in CPP):

Solution:
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cassert>
#include<map>
#include<set>
#include<climits>
#include<cstring>

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)

using namespace std;

#define FIR 1
#define SEC 0

short h,w,memo[22][22][22][22];
string s[21];

short dfs(int xL,int yL,int xR,int yR,int phase) {
  if( !( xL < xR && yL < yR ) ) {
    return 0;
  }
  short &grundy = memo[xL][yL][xR][yR];
  if( grundy != -1 ) return grundy;
  set<int> S;
  REP(y,yL,yR) {
    REP(x,xL,xR) {
      if( s[y][x] == 'X') continue;
      int v = 0;
      v ^= dfs(xL,yL,x,y,(phase+1)&1);
      v ^= dfs(x+1,yL,xR,y,(phase+1)&1);
      v ^= dfs(xL,y+1,x,yR,(phase+1)&1);
      v ^= dfs(x+1,y+1,xR,yR,(phase+1)&1);
      S.insert(v);
    }
  }
  rep(i,1000) if( !S.count(i) ) {
    grundy = i;
    break;
  }
  return grundy;
}

void compute() {
  memset(memo,-1,sizeof memo);
  puts(dfs(0,0,w,h,FIR)?"First":"Second");
}

int main() {
  if( 0 ) {
    srand((unsigned int)time(NULL));
    h = 4, w = 4;
    cout << h << " " << w << endl;
    rep(i,h) {
      rep(j,w) {
	cout << ((rand()%2)?'X':'.');
      }puts("");
    }
    return 0;
  }
  cin >> h >> w;
  rep(i,h) cin >> s[i];
  compute();
  return 0;
}