Problem: Example

Input

2 2
..
..


Output

Second

Solution (in CPP):

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

int h,w;
string field[25];
int memo[25][25][25][25];

int calc(int x1,int x2,int y1,int y2){
	if(x1 == x2 || y1 == y2) return 0;
	if(memo[x1][x2][y1][y2] != -1) return memo[x1][x2][y1][y2];
	set<int> st;
	for(int i = x1;i < x2;i++){
		for(int j = y1;j < y2;j++){
			if(field[i][j] == 'X') continue;
			int g = calc(x1,i,y1,j) ^ calc(i+1,x2,y1,j) ^ calc(x1,i,j+1,y2) ^ calc(i+1,x2,j+1,y2);
			st.insert(g);
		}
	}
	for(int i = 0;;i++){
		if(!st.count(i)) return memo[x1][x2][y1][y2] = i;
	}
}

signed main(){
	cin >> h >> w;
	for(int i = 0;i < h;i++) cin >> field[i];
	for(int i = 0;i <= h;i++){
		for(int j = 0;j <= h;j++){
			for(int k = 0;k <= w;k++){
				for(int l = 0;l <= w;l++) memo[i][j][k][l] = -1;
			}
		}
	}
	if(calc(0,h,0,w)) cout << "First" << endl;
	else cout << "Second" << endl;
}