Problem: Example

Input

2 2
..
..


Output

Second

Solution (in CPP):

Solution:
#include <iostream>
#include <vector>
#include <string>
#include <functional>
#include <set>

template <class T>
std::vector<T> vec(int len, T elem) { return std::vector<T>(len, elem); }

void solve() {
    int h, w;
    std::cin >> h >> w;

    std::vector<std::string> ss(h);
    for (auto& s : ss) std::cin >> s;

    auto dp = vec(h, vec(h, vec(w, vec(w, -1))));

    std::function<int(int, int, int, int)>
        dfs = [&](int lx, int rx, int ly, int ry) {
            if (rx < lx || ry < ly) return 0;

            auto& ret = dp[lx][rx][ly][ry];
            if (ret != -1) return ret;

            std::set<int> gs;
            for (int x = lx; x <= rx; ++x) {
                for (int y = ly; y <= ry; ++y) {
                    if (ss[x][y] == 'X') continue;

                    int g = dfs(lx, x - 1, ly, y - 1) ^
                            dfs(x + 1, rx, ly, y - 1) ^
                            dfs(lx, x - 1, y + 1, ry) ^
                            dfs(x + 1, rx, y + 1, ry);
                    gs.insert(g);
                }
            }

            for (int i = 0;; ++i) {
                if (!gs.count(i)) {
                    ret = i;
                    break;
                }
            }
            return ret;
        };

    int g = dfs(0, h - 1, 0, w - 1);
    std::cout << (g == 0 ? "Second" : "First") << std::endl;
}

int main() {
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);

    solve();

    return 0;
}