Problem: Example

Input

2 2
..
..


Output

Second

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF 1e16
#define mod 1000000007

int h,w;
string s[22];
int dp[22][22][22][22];

int dfs(int i1,int j1,int i2,int j2){
  if(i1>=i2||j1>=j2)return 0;
  if(dp[i1][j1][i2][j2]!=-1)return dp[i1][j1][i2][j2];
  set<int> st;
  rep(i,20)rep(j,20)st.insert(i*w+j);
  repl(i,i1,i2)repl(j,j1,j2){
    if(s[i][j]=='X')continue;
    int sum=0;
    sum^=dfs(i1,j1,i,j);
    sum^=dfs(i+1,j1,i2,j);
    sum^=dfs(i1,j+1,i,j2);
    sum^=dfs(i+1,j+1,i2,j2);
    st.erase(sum);
  }
  return dp[i1][j1][i2][j2]=*st.begin();
}

int main(){
  cin>>h>>w;
  rep(i,h)cin>>s[i];
  memset(dp,-1,sizeof(dp));
  int res=dfs(0,0,h,w);
  if(res==0)cout<<"Second"<<endl;
  else cout<<"First"<<endl;
  return 0;
}