Problem: Example

Input

2 2
..
..


Output

Second

Solution (in CPP):

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

using namespace std;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a, 0, sizeof a)
#define minus(a) memset(a, -1, sizeof a)
#define watch(a) { cout << #a << " = " << a << endl; }
template<class T1, class T2> inline bool minimize(T1 &a, T2 b) { return b < a && (a = b, 1); }
template<class T1, class T2> inline bool maximize(T1 &a, T2 b) { return a < b && (a = b, 1); }

typedef long long ll;
int const inf = 1<<29;

int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};

int memo[22][22][22][22];
int H, W;
string G[22];

int solve(int sy, int sx, int gy, int gx) {

  if(sy == gy || sx == gx) return 0;

  int& ret = memo[sy][sx][gy][gx];
  if(ret + 1) return ret;

  set<int> s;
  REP(i, sy, gy) REP(j, sx, gx) {
    if(G[i][j] == 'X') continue;
    int a = solve(sy, sx, i, j);
    int b = solve(sy, j + 1, i, gx);
    int c = solve(i + 1, sx, gy, j);
    int d = solve(i + 1, j + 1, gy, gx);
    s.insert(a ^ b ^ c ^ d);
  }

  int r = 0;
  while(s.count(r)) r++;

  return ret = r;
}

int main() {

  minus(memo);

  cin >> H >> W;
  rep(i, H) cin >> G[i];
  cout << (solve(0, 0, H, W) > 0 ? "First" : "Second") << endl;
  
  return 0;
}