Problem: Example

Input

2 2
..
..


Output

Second

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
using T = tuple<int, int, int, int>;

map<T, int> dp;
char is[20][20];
int H, W;

int find(int I, int J, int K, int L) {
	if (I == J || K == L) {
		return 0;
	}
	if (dp[make_tuple(I, J, K, L)]) {
		return dp[make_tuple(I, J, K, L)] - 1;
	}
	vector<int> ko;
	for (int i = I; i < J; i++) {
		for (int j = K; j < L; j++) {
			if (is[i][j] == '.') {
				ko.push_back(find(I, i, K, j) ^ find(i + 1, J, K, j) ^ find(I, i, j + 1, L) ^ find(i + 1, J, j + 1, L));
			}
		}
	}
	sort(ko.begin(), ko.end());
	ko.erase(unique(ko.begin(), ko.end()), ko.end());
	int res = 0;
	while (res < (int)ko.size() && ko[res] == res) {
		res++;
	}
	dp[make_tuple(I, J, K, L)] = res + 1;
	return res;
}

int main()
{
	cin >> H >> W;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			cin >> is[i][j];
		}
	}
	cout << (find(0, H, 0, W) ? "First" : "Second") << endl;
	return 0;
}