Problem: Example

Input

2 2
..
..


Output

Second

Solution (in CPP):

Solution:
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;
const ld eps=1e-9;

//// < "D:\D_Download\Visual Studio 2015\Projects\programing_contest_c++\Debug\a.txt"

int memo[22][22][22][22];


int getnum(const vector<vector<int>>&field,const int l,const int r,const int u,const int d) {
	if (memo[l][r][u][d] != -1)return memo[l][r][u][d];
	if (l == r)return 0;
	else if (u == d)return 0;
	else {
		assert(l < r);
		assert(u < d);
		set<int>nums;
		for (int x = l; x < r; ++x) {
			for (int y = u; y < d; ++y) {
				if (field[y][x])continue;
				else {
					int anum = 0;
					anum ^= getnum(field, l, x, u, y);
					anum ^= getnum(field, x + 1, r, u, y);
					anum ^= getnum(field, l, x, y + 1, d);
					anum ^= getnum(field, x + 1, r, y + 1, d);
					nums.emplace(anum);
				}
			}
		}
		int ans = 0;
		auto it = nums.begin();
		while (it != nums.end()) {
			if (ans == *it) {
				ans++;
				it++;
			}
			else {
				break;
			}
		}
		return memo[l][r][u][d]=ans;
	}
}

int main() {
	int H, W; cin >> H >> W;
	for (int i = 0; i < 22; ++i) {
		for (size_t j = 0; j < 22; j++)
		{
			for (size_t k = 0; k < 22; k++)
			{
				for (size_t l = 0; l < 22; l++)
				{
					memo[i][j][k][l] = -1;
				}
			}
		}
	}
	vector<vector<int>>field(H, vector<int>(W));
	for (int i = 0; i < H; ++i) {
		string st; cin >> st;
		for (int j = 0; j < W; ++j) {
			if (st[j] == '.') {
				field[i][j] = false;
			}
			else {
				field[i][j] = true;
			}
		}
	}
	int ans = getnum(field,0, W, 0, H);
	if (ans) {
		cout << "First" << endl;
	}
	else {
		cout << "Second" << endl;
	}
	return 0;

}