AtCoder-ABC196 D - Hanjo【Python解答例】
AtCoder Beginner Contest196のD - HanjoについてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 196 - AtCoder
AtCoder Beginner Contest196 D - Hanjo
問題文
縦 H メートル、横 W メートルの長方形の部屋があります。
この部屋に 2 メートル × 1 メートルの区別できない畳 (長方形のタイル) A 枚と、1 メートル × 1 メートルの区別できない半畳 (正方形のタイル) B 枚を敷き詰めます。
2 メートル × 1 メートルの畳は縦長にも横長にも使うことができます。
敷き詰める方法は何通りあるでしょうか？
なお、2A+B=HW であることが保証されます。 また、回転や反転を行うことで初めて一致するような敷き詰め方は区別します。
制約
・入力は全て整数
・1≤H,W
・HW≤16
・0≤A,B
・2A+B=HW
解答例
h, w, a, b = map(int,input().split()) used = [[0]*w for _ in range(h)] # 畳があるか管理 res = 0 # マス(1,1)から(1,w)、(2,1)から(2,w)・・・(h,1)から(h,w)の順にdfs def dfs(i,j,a,b): global res if a<0 or b<0: # 畳がa枚以下やb枚以下になれば失敗 return if j == w: # 右端に来たら次の行へ j = 0 i += 1 if i == h: # iがhになれば成功(条件にあう畳の敷き詰め方) res += 1 return if used[i][j] == 1: # 調べるマスに畳があれば次のマスに return dfs(i,j+1,a,b) used[i][j] = 1 dfs(i,j+1,a,b-1) # 半畳 使う場合 if j+1 < w and used[i][j+1] == 0: #横に1畳置く場合 used[i][j+1] = 1 dfs(i,j+1,a-1,b) used[i][j+1] = 0 if i+1 < h and used[i+1][j] == 0: #縦に1畳置く場合 used[i+1][j] = 1 dfs(i,j+1,a-1,b) used[i+1][j] = 0 used[i][j] = 0 # 元に戻す return res print(dfs(0,0,a,b))
解説
縦H、横Wの部屋において、1畳(2マス分)の畳をA枚と、半畳(1マス分)の畳をB枚の敷き詰め方が何通りあるか答える問題です。
公式解説動画のようにDFSを用いた解法になります。
DFSでは左上マス(1,1)から(1,w)、(2,1)から(2,w)・・・(h,1)から(h,w)のように横書き文章の順に進めていきました。
関数では終了条件から書いています。
ひとつ目の終了条件は畳の枚数aやbがマイナスになれば終了しています。
畳を使いすぎれば失敗です。
2つ目は終了条件ではないですが、右端のマスを探索した後に次の行に移る動きをさせています。
3つ目は途中で畳が足りなくなったりしないで全マス探索し終えたことになるので、求める置き方ができたことになります。
したがってresに1を足しました。
4つ目は今、探索しているマスにすでに畳が置かれている状態なので、なにもしないで次のマスに移ります。
次からは遷移の部分です。
まず、現在のマスに畳を置かれたことをusedリストに記録します。
そこから3通りに分岐します。
・半畳の畳を置く場合
半畳の畳はどこでもおけるので、次のマス目に移動し半畳の畳を1枚引いて再度DFSします。
・1畳の畳を横に置く場合
現在のマスの右横に畳をおけるなら探索します。
右横のマスに畳を置いたことをusedにメモして、次のマス目から1畳の畳を1枚引いて再度DFSしました。
このDFS関数から戻ったとき、以降の探索のため右横の畳は消しておきます。
・1畳の畳を縦に置く場合
同じように現在のマスの下に畳をおけるなら探索します。
同様に下マスに畳を置いたことをusedにメモし、次のマス目から1畳の畳を1枚引いて再度DFSです。
このDFS関数から戻ったときも、下の畳は消しておきました。
このDFSによりi == hとなった数を数えることで、畳の敷き詰め方がわかります。
最後にresを出力すればOKでした。
ABC196の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com
