Problem: Example

Input

2 2
..
..


Output

Second

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
#define y1 Gacho
#define N 20
using namespace std;

string s[N];
int h, w, X[N][N];
int grundy[N][N][N][N];

int dfs(int y1, int y2, int x1, int x2){
  
  if(y2-y1<0||x2-x1<0) return 0;
  
  int &g=grundy[y1][y2][x1][x2];
  
  if(g!=-1) return g;
    
  set<int> S;
  
  for(int i=y1;i<=y2;i++)
    for(int j=x1;j<=x2;j++){
      if(X[i][j]) continue;
      int a=dfs(y1,i-1,x1,j-1);
      int b=dfs(y1,i-1,j+1,x2);
      int c=dfs(i+1,y2,x1,j-1);
      int d=dfs(i+1,y2,j+1,x2);
      S.insert(a^b^c^d);
    }
  
  int cnt=0;
  
  while(S.count(cnt)) cnt++;
  
  return g=cnt;
}

void solve(){

  memset(grundy,-1,sizeof(grundy));
  
  cout<<(dfs(0, h-1, 0, w-1)?"First":"Second")<<endl;
  
}

int main(){

  cin>>h>>w;

  for(int i=0;i<h;i++){
    cin>>s[i];
    for(int j=0;j<w;j++)
      if(s[i][j]=='X') X[i][j]=1;
  }

  solve();
  
  return 0;
}