ABC196 D Hanjo
公式解説とは少し方法が違う.
まず半畳の位置をbit全探索して固定する(これはnext_combinationを用いて行うと高速だが, $ B = 0の場合通常の関数の場合例外処理しなければならないことに注意). その後DFSをして畳を敷いていく. この際, いくら制約が小さくても計算量が爆発してしまうので, 4進数(0→おかれていない, 1→半畳, 2→縦長畳, 3→横長畳)を状態として持ってメモ化再帰していけばよい.
計算量は多く見積もっても$ O(_{HW} C _B HW2^A)となり, これはこの問題の制約の場合十分高速である.
再帰で重要なのは, 終了条件を書き忘れないこと, 遷移を正確に行うことである.