[アルゴリズム]負モード負モード

https://www.acmicpc.net/problem/14712
質問する
スカーフ枚××× ゲームに深く感染し、矩形の格子板と「知母」という謎の生物を利用した「知母知母」ゲームを制作した.このゲームのルールは簡単です.ランダムに1つのチェックボードのスペースを選択して「帽子」または4つの「帽子」のチェック2を配置します.× 2つの長方形になっている部分を見つけて、上の「毛を引く」ことに飽きてしまうまで繰り返します.

しかし残念なことに、ゲームは本当に面白くなくて、ニモはすぐに飽きてしまいました.がっかりしたニモは適当にゲームをすることにし、「ラモ」を外そうとしたが、格子板の「ラモ」を外せなかったらゲームをやめた.ニモがゲームを終了する時に現れる可能性のある「ニモ」レイアウトの偽数を求めます.
入力
第1行目のグリッドプレート上の行数N,列数M(1≦N,M≦25,1≦N)× M≦25)は空白に分割される.
しゅつりょく
最初の行に指定されたグリッドボードに表示される「斜角」セルは2つあります.× 2矩形を構成しないすべてのレイアウトのダミー数を出力します.

import sys


def dfs(cnt):
    global answer
    # 모든 칸을 확인한 경우 정답 1개 카운트
    if cnt == Y * X:
        answer += 1
        return

    # 현재 좌표
    y, x = cnt // X, cnt % X

    # 좌표가 범위내에 있는경우
    # 상, 좌, 상좌 위치에 네모가 있으면 바로 다음 칸확인
    if (0 < y < Y and 0 < x < X) and (arr[y - 1][x] and arr[y][x - 1] and arr[y - 1][x - 1]):
        dfs(cnt + 1)
    # 네모가 없는 경우
    else:
        # 네모 추가한 경우 확인
        arr[y][x] = 1
        dfs(cnt + 1)
        # 추가하지 않은 경우 확인
        arr[y][x] = 0
        dfs(cnt + 1)


Y, X = map(int, sys.stdin.readline().split())
arr = [[0] * X for _ in range(Y)]
answer = 0
dfs(0)
print(answer)