Problem: Example

Input

2 2
..
..


Output

Second

Solution (in CPP):

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

int n,m;
char _map[nn][nn];
int dp[nn][nn][nn][nn];


int dfs(int x1,int y1,int x2,int y2){
	if(x1>x2 or y1>y2) return 0;
	if(dp[x1][y1][x2][y2]>-1) return dp[x1][y1][x2][y2];
	set<int> all;
	for(int i=x1;i<=x2;i++) {
		for(int j=y1;j<=y2;j++) if(_map[i][j]=='.'){
			int w=dfs(x1,y1,i-1,j-1)^dfs(x1,j+1,i-1,y2)^dfs(i+1,y1,x2,j-1)^dfs(i+1,j+1,x2,y2);
			all.insert(w);
		}
	}
	int res=0;
	while(all.count(res))res++;

	return dp[x1][y1][x2][y2]=res;
}

int main(){
	memset(dp,-1,sizeof dp);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%s",_map[i]+1);
	
	if(dfs(1,1,n,m)) puts("First");else puts("Second");	
	return 0;
}