Problem:
Problem L
Wall Making Game The game Wall Making Game , a two-player board game, is all the rage. This game is played on an $H \times W$ board. Each cell of the board is one of empty , marked , or wall . At the beginning of the game, there is no wall on the board. In this game, two players alternately move as follows:  A player chooses one of the empty cells (not marked and not wall). If the player can't choose a cell, he loses.  Towards each of the four directions (upper, lower, left, and right) from the chosen cell, the player changes cells (including the chosen cell) to walls until the player first reaches a wall or the outside of the board.  Note that marked cells cannot be chosen in step 1, but they can be changed to walls in step 2. Fig.1 shows an example of a move in which a player chooses the cell at the third row and the fourth
column.  Fig.1: An example of a move in Wall Making Game. Your task is to write a program that determines which player wins the game if the two players play optimally from a given initial board. Input The first line of the input consists of two integers $H$ and $W$ $(1 \leq H, W \leq 20)$, where $H$ and $W$ are the height and the width of the board respectively. The following $H$ lines represent the initial board. Each of the $H$ lines consists of $W$ characters. The $j$-th character of the $i$-th line is ' . ' if the cell at the $j$-th column of the $i$-th row is empty, or ' X ' if the cell is marked. Output Print " First " (without the quotes) in a line if the first player wins the given game. Otherwise, print " Second " (also without the quotes) in a line. Sample Input 1 2 2
..
.. Output for the Sample Input 1 Second Sample Input 2 2 2
X.
.. Output for the Sample Input 2 First Sample Input 3 4 5
X....
...X.
.....
..... Output for the Sample Input 3 First

Solution (Python):
import sys
readline = sys.stdin.readline
write = sys.stdout.write
def solve():
    H, W = map(int, readline().split())
    f = ".X".index
    S = [list(map(f, readline().strip())) for i in range(H)]
    memo = {}
    def dfs(px, py, qx, qy):
        key = (px, py, qx, qy)
        if key in memo:
            return memo[key]
        res = set()
        for y in range(py, qy):
            for x in range(px, qx):
                if S[y][x]:
                    continue
                r1 = dfs(px, py, x, y)
                r2 = dfs(x+1, py, qx, y)
                r3 = dfs(px, y+1, x, qy)
                r4 = dfs(x+1, y+1, qx, qy)
                res.add(r1 ^ r2 ^ r3 ^ r4)
        k = 0
        while k in res:
            k += 1
        memo[key] = k
        return k
    if dfs(0, 0, W, H):
        write("First\n")
    else:
        write("Second\n")
solve()