Problem: Example

Input

2 2
..
..


Output

Second

Solution (in CPP):

Solution:
#include <set>
#include <string>
#include <iostream>
using namespace std;
int H, W, vis[22][22][22][22], 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 (vis[x1][y1][x2][y2]) return dp[x1][y1][x2][y2];
	set<int> s_;
	for (int i = y1; i < y2; i++) {
		for (int j = x1; j < x2; j++) {
			if (s[i][j] == 'X') continue;
			int res1 = rec(x1, y1, j, i);
			int res2 = rec(x1, i + 1, j, y2);
			int res3 = rec(j + 1, y1, x2, i);
			int res4 = rec(j + 1, i + 1, x2, y2);
			int res5 = res1 ^ res2 ^ res3 ^ res4;
			s_.insert(res5);
		}
	}
	vis[x1][y1][x2][y2] = true;
	int ret = 0;
	while (s_.count(ret)) ret++;
	return dp[x1][y1][x2][y2] = ret;
}
int main() {
	cin >> H >> W;
	for (int i = 0; i < H; i++) cin >> s[i];
	int ret = rec(0, 0, W, H);
	if (ret > 0) cout << "First" << endl;
	else cout << "Second" << endl;
	return 0;
}