게임판 덮기

import sys


WHITE = '.'
BLACK = '#'


def solve(board, width, height, x, y):
    while board[y][x] == BLACK:
        index = y*width + x
        index += 1
        y, x = index // width, index % width

        if y == height:
            return 1

    answer = 0
    patterns_x = [(x, x  , x+1), (x, x+1, x  ), (x, x+1, x+1), (x, x-1, x  )]
    patterns_y = [(y, y+1, y+1), (y, y  , y+1), (y, y  , y+1), (y, y+1, y+1)]
    for pattern_x, pattern_y in zip(patterns_x, patterns_y):
        if not (0 <= min(pattern_x) and max(pattern_x) < width and max(pattern_y) < height):
            continue
        tmp_board = [row.copy() for row in board]
        for tx, ty in zip(pattern_x, pattern_y):
            if tmp_board[ty][tx] == BLACK:
                break
            tmp_board[ty][tx] = BLACK
        else:
            answer += solve(tmp_board, width, height, x, y)
    return answer


if __name__ == "__main__":
    n_testcases = int(sys.stdin.readline())

    for t in range(n_testcases):
        height, width = map(int, sys.stdin.readline().split())
        board = []
        for y in range(height):
            board.append(list(sys.stdin.readline().rstrip()))

        print(solve(board, width, height, 0, 0))