Problem: Example

Input

2 2
..
..


Output

Second

Solution (in CPP):

Solution:
#include <iostream>
#include <set>

using namespace std;

int H, W;
char map[25][25];
int memo[25][25][25][25];

int calc(int sx, int sy, int tx, int ty)
{
	if(sx > tx || sy > ty) return 0;
	if(memo[sx][sy][tx][ty] != -1) return memo[sx][sy][tx][ty];
	
	int g;
	set<int> s;
	for(int x = sx; x <= tx; x++){
		for(int y = sy; y <= ty; y++){
			if(map[x][y] == 'X') continue;
			g = 0;
			g ^= calc(sx, sy, x-1, y-1);
			g ^= calc(x+1, sy, tx, y-1);
			g ^= calc(sx, y+1, x-1, ty);
			g ^= calc(x+1, y+1, tx, ty);
			s.insert(g);
		}
	}
	int ret = 0;
	while(s.count(ret)) ret++;
	return memo[sx][sy][tx][ty] = ret;
}

int main(void)
{
	cin >> H >> W;
	for(int y = 0; y < H; y++){
		for(int x = 0; x < W; x++){
			cin >> map[x][y];
		}
	}
	
	for(int sx = 0; sx < W; sx++){
		for(int sy = 0; sy < H; sy++){
			for(int tx = 0; tx < W; tx++){
				for(int ty = 0; ty < H; ty++){
					memo[sx][sy][tx][ty] = -1;
				}
			}
		}
	}
	if(calc(0, 0, W-1, H-1)) cout << "First" << endl;
	else cout << "Second" << endl;
	
	return 0;
}