Problem: Example

Input

2 2
..
..


Output

Second

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;

const int S = 22;
int dp[S][S][S][S];
char m[S][S];

bool used[S*S];
int mex(const vector<int> &vec)
{
    for(auto x: vec)
        used[x] = true;
    int ans;
    for(int i = 0; ; i++)
        if(!used[i])
        {
            ans = i;
            break;
        }
    for(auto x: vec)
        used[x] = false;
    return ans;
}

int main()
{
    int h, w;
    scanf("%d %d", &h, &w);
    for(int i = 1; i <= h; i++)
        scanf("%s", m[i] + 1);
    for(int i = 0; i < h; i++)
        for(int j = 0; j < w; j++)
            for(int x0 = 1; x0 + i <= h; x0++)
                for(int y0 = 1; y0 + j <= w; y0++)
                {
                    int x1 = x0 + i, y1 = y0 + j;
                    vector<int> vec;
                    for(int x = x0; x <= x1; x++)
                        for(int y = y0; y <= y1; y++)
                            if(m[x][y] == '.')
                                vec.push_back(dp[x0][x-1][y0][y-1]
                                            ^ dp[x+1][x1][y0][y-1]
                                            ^ dp[x0][x-1][y+1][y1]
                                            ^ dp[x+1][x1][y+1][y1]);
                    dp[x0][x1][y0][y1] = mex(vec);
                }
    puts(dp[1][h][1][w] ? "First" : "Second");
}