Problem: Example

Input

2 2
..
..


Output

Second

Solution (in CPP):

Solution:
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

int H,W;
char table[20][21];

int dp[20][20][20][20];

int grundy(int row1,int col1,int row2,int col2){

	if(row1 > row2 || col1 > col2)return 0;

    if(dp[row1][col1][row2][col2] != -1)return dp[row1][col1][row2][col2];

    set<int> S;

    for(int row = row1; row <= row2; row++){
    	for(int col = col1; col <= col2; col++){
    		 if(table[row][col]=='X')continue;

    		 int x = 0;
    		 x ^= grundy(row1,col1,row-1,col-1);
    		 x ^= grundy(row1,col+1,row-1,col2);
    		 x ^= grundy(row+1,col1,row2,col-1);
    		 x ^= grundy(row+1,col+1,row2,col2);
    		 S.insert(x);
    	}
    }

    int g = 0;
    while(S.count(g) != 0)g++;

    return dp[row1][col1][row2][col2] = g;
}


int main(){

	scanf("%d %d",&H,&W);

	for(int row = 0; row < H; row++){
		scanf("%s",table[row]);
	}

    for(int a = 0; a < H; a++){
    	for(int b = 0; b < W; b++){
    		for(int c = 0; c < H; c++){
    			for(int d = 0; d < W; d++){
    				dp[a][b][c][d] = -1;
    			}
    		}
    	}
    }

	if(grundy(0,0,H-1,W-1) != 0){
		printf("First\n");
	}else{
    	printf("Second\n");
    }
}