[AOJ] No. 0632 休憩スペース (Refreshment Area)

2019年7月2日

問題

方針

縦方向と横方向に分けて考える

休憩スペースは南北方向または東西方向に置くことが可能なので、縦方向と横方向に分けて考えます。

連続する空マスを数える

ある方向に向かって連続する空マスを数え、その値が \( D \) よりも大きい時、そのマスを末端として休憩スペースを置くことができます。つまり、休憩スペースの末端を調べることで休憩スペースを設けるパターンの場合の数が分かります。

コード