Problem: Example

Input

2 2
..
..


Output

Second

Solution (in CPP):

Solution:
#include<iostream>
#include<set>
using namespace std;
int dp[21][21][21][21];
int H, W, x[20][20];
int solve(int a1, int b1, int a2, int b2) {
	if (a1 > a2 || b1 > b2)return 0;
	if (dp[a1][b1][a2][b2] >= 0)return dp[a1][b1][a2][b2];
	set<int>S;
	for (int i = a1; i <= a2; i++) {
		for (int j = b1; j <= b2; j++) {
			if (x[i][j] == 1)continue;
			int V1 = solve(a1, b1, i - 1, j - 1);
			int V2 = solve(a1, j + 1, i - 1, b2);
			int V3 = solve(i + 1, b1, a2, j - 1);
			int V4 = solve(i + 1, j + 1, a2, b2);
			int V5 = V1 ^ V2 ^ V3 ^ V4;
			S.insert(V5);
		}
	}
	for (int i = 0; i < 400; i++) {
		if (S.count(i) == 0) { dp[a1][b1][a2][b2] = i; break; }
	}
	return dp[a1][b1][a2][b2];
}
int main() {
	cin >> H >> W;
	for (int i = 0; i < 441; i++) {
		for (int j = 0; j < 441; j++)dp[i / 21][i % 21][j / 21][j % 21] = -1;
	}
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			char p; cin >> p;
			if (p == 'X')x[i][j] = 1;
		}
	}
	int res = solve(0, 0, H - 1, W - 1);
	if (res == 0)cout << "Second" << endl;
	else { cout << "First" << endl; }
	return 0;
}