Problem: Example

Input

2 2
..
..


Output

Second

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
#define MAX 22
#define inf 1<<29
#define linf (1e16)
#define eps (1e-8)
#define Eps (1e-15)
#define mod 1000000007
#define pi acos(-1.0)
#define phi (1.0+sqrt(5.0))/2.0
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define pd(a) printf("%.10f\n",(double)(a))
#define pld(a) printf("%.10Lf\n",(ld)(a))
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(a)-1;(b)<=i;i--)
#define Unique(v) v.erase(unique(all(v)),v.end())
#define equals(a,b) (fabs((a)-(b))<eps)
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<int,double> pid;
typedef pair<double,int> pdi;
typedef pair<double,double> pdd;
typedef vector<int> vi;
typedef vector<pii> vpi;

int h,w;
int mem[MAX][MAX][MAX][MAX];
string grid[MAX];

int rec(int a,int b,int c,int d){
  if(mem[a][b][c][d]!=-1)return mem[a][b][c][d];

  set<int> s;
  FOR(i,a,c){
    FOR(j,b,d){
      if(grid[i][j]=='X')continue;
      int g=0;
      if(i!=a && j!=b)g^=rec(a,b,i,j);
      if(i!=a && j!=d-1)g^=rec(a,j+1,i,d);
      if(i!=c-1 && j!=b)g^=rec(i+1,b,c,j);
      if(i!=c-1 && j!=d-1)g^=rec(i+1,j+1,c,d);
      s.insert(g);
    }
  }
  int res=0;
  while(s.count(res))res++;
  mem[a][b][c][d]=res;
  return res;
}

int main()
{
  cin>>h>>w;
  FOR(i,0,h)cin>>grid[i];
  memset(mem,-1,sizeof(mem));
  if(rec(0,0,h,w)!=0)cout<<"First"<<endl;
  else cout<<"Second"<<endl;

  return 0;
}