ABC196 D問題 Hanjoを解く

解けなかったABC196のD問題を反省しながらふりかえります。

atcoder.jp

高さHと幅Wのスペースと、半畳の畳A枚と、1畳の畳B枚が与えられて、スペースをピッタリ埋められるパターン数を導く問題です。
なので、全探索できそうな雰囲気を感じとります。計算量の詳細は公式解説がわかりやすいです。
全探索するときに深さ優先探索(Depth First Search)ですることを考えて、
あるマスの座標(i, j)を埋める時に残りA枚、B枚の時に何パターンあるか返す関数を定義します。

探索する順番としては、左上から始めて、次に右隣、右端にぶつかったら、一段下がって左端から探索します。

探索順序

ある地点が畳で埋まっているか記録しながら探索します。ここではusedという2次元配列を使いました。

深さ優先探索を実装するときのポイントをいくつか取り上げます。

探索の分岐は3つ

基本は、半畳、右へ伸ばすように（横に）1畳、下へ伸ばすように（縦に）1畳、の3つの分岐を広げていきます。

深さ優先探索のイメージ

再帰関数から戻ったら畳で埋まっていないようにする

これは途中で気づきましたが。。。すんなりとは気づけませんでした。
深さ優先探索で次の階層の探索、例えば、座標(i, j+1)のに入るときは、座標(i, j+1)が畳で埋まっているようにして、再帰関数を呼び出します。再帰関数から値が返ってきたら1つ上の深さに戻るのでスペースは埋まっていない状態にします。

used[i][j + 1] = True
res += dfs(i, j + 1, a - 1, b)
# 1つ上の深さに戻るので未使用にする
used[i][j + 1] = False

終了条件

再帰処理するときは終了条件を与えないと無限ループします。

returnの条件は以下の2つです。

途中でどちらかの畳を使い切ったらカウントせず0を返す
i == Hになったら一番最後の右端まで到達したことになる、つまり畳で埋めきったので1カウントする

H, W, A, B = map(int, input().split())

# 畳で埋まってるかどうかを記録
used = [[False for _ in range(16)] for _ in range(16)]


def dfs(i: int, j: int, a: int, b: int):
    # どちらかの畳を使い切る
    if a < 0 or b < 0:
        return 0
    # 一番右端に来た時に、左端に戻しつつ下を見る
    if j == W:
        j = 0
        i += 1
    # 一番下に到達したら終了
    if i == H:
        return 1
    # 畳で埋まってたら右隣を探索
    if used[i][j]:
        return dfs(i, j + 1, a, b)
    res = 0
    used[i][j] = True
    # 半畳を使った場合
    res += dfs(i, j + 1, a, b - 1)
    # 横にAを置く場合
    # j + 1 がWに収まってて、i, j+1が埋まってない
    if j + 1 < W and not used[i][j + 1]:
        used[i][j + 1] = True
        res += dfs(i, j + 1, a - 1, b)
        # 1つ上の深さに戻るので未使用にする
        used[i][j + 1] = False
    # 縦にAを置く場合
    # i + 1がHに収まってて、i + 1, j が埋まってない
    if i + 1 < H and not used[i + 1][j]:
        used[i + 1][j] = True
        res += dfs(i, j + 1, a - 1, b)
        # 1つ上の深さに戻るので未使用にする
        used[i + 1][j] = False
    used[i][j] = False
    return res


# 左上から探索開始
print(dfs(0, 0, A, B))

再帰処理はまだ全然慣れてないので、3日後にまた解こうとおもいます。