Problem: Example

Input

2 2
..
..


Output

Second

Solution (in CPP):

Solution:
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;


int dp[22][22][22][22];

string s[22];
int rec(int x1,int y1,int x2,int y2){
    if(x1>x2||y1>y2)return 0;
    if(dp[x1][y1][x2][y2]!=-1)return dp[x1][y1][x2][y2];
    vector<int> g;
    REP(i,x1,x2+1)REP(j,y1,y2+1){
        if(s[i][j]=='X')continue;
        int ret=0;
        ret^=rec(x1,y1,i-1,j-1);
        ret^=rec(x1,j+1,i-1,y2);
        ret^=rec(i+1,y1,x2,j-1);
        ret^=rec(i+1,j+1,x2,y2);
        g.push_back(ret);
    }
    sort(g.begin(),g.end());
    g.erase(unique(g.begin(),g.end()),g.end());
    g.push_back(inf);
    rep(i,g.size()){
        if(g[i]!=i){
            return dp[x1][y1][x2][y2]=i;
        }
    }
    return -1;
}

int main(){
    int h,w;
    cin>>h>>w;
    rep(i,h)cin>>s[i];
    rep(i,h)rep(j,w)rep(k,h)rep(l,w)dp[i][j][k][l]=-1;
    int ans = rec(0,0,h-1,w-1);
    cout<<(ans?"First" : "Second")<<endl;
    return 0;
}