Problem:
Problem I: Tatami A tatami mat, a Japanese traditional floor cover, has a rectangular form with aspect ratio 1:2. When
spreading tatami mats on a floor, it is prohibited to make a cross with the border of the tatami mats,
because it is believed to bring bad luck. Your task is to write a program that reports how many possible ways to spread tatami mats of the same
size on a floor of given height and width. Input The input consists of multiple datasets. Each dataset cosists of a line which contains two integers H and W in this order, separated with a single
space. H and W are the height and the width of the floor respectively. The length of the shorter edge of a
tatami mat is regarded as a unit length. You may assume 0 < H , W ≤ 20. The last dataset is followed by a line containing two zeros. This line is not a part of any dataset and should not be processed. Output For each dataset, print the number of possible ways to spread tatami mats in one line. Sample Input 3 4
4 4
0 0 Output for the Sample Input 4
2

Solution (Python):
def solve():
    H, W = map(int, input().split())
    if H == 0:
        return False
    if H*W % 2 == 1:
        print(0)
        return True
    state = [[-1]*W for i in range(H)]
    def dfs(k):
        if k == H*W:
            return 1
        i, j = divmod(k, W)
        if state[i][j] != -1:
            return dfs(k+1)
        if i > 0 and j > 0 and state[i-1][j-1] != state[i-1][j] != state[i][j-1] != state[i-1][j-1]:
            return 0
        r = 0
        state[i][j] = k
        if i+1 < H:
            state[i+1][j] = k
            r += dfs(k+1)
            state[i+1][j] = -1
        if j+1 < W and state[i][j+1] == -1:
            state[i][j+1] = k
            r += dfs(k+1)
            state[i][j+1] = -1
        state[i][j] = -1
        return r
    print(dfs(0))
    return True
while solve():
    ...