题解 | #走方格的方案数#DFS做法

def dfs(i, j):
    if i == n and j == m:
        temp.append(1)
        return

    for k in range(2):
        x = i + dx[k]
        y = j + dy[k]
        if (0 <= x <= n) and (0 <= y <= m) and maze[x][y] == 0:
            maze[x][y] = 1
            dfs(x, y)
            maze[x][y] = 0
    else:
        return


while True:
    try:
        n, m = map(int, input().strip().split(' '))
        maze = [[0] * (m + 1) for _ in range(n + 1)]
        dx = [0, 1]
        dy = [1, 0]
        temp = []
        dfs(0, 0)
        print(len(temp))
    except:
        break