AT_tenka1_2013_qualB_c 天下一ジグソーパズルふたたび

[problemUrl]: https://atcoder.jp/contests/tenka1-2013-qualb/tasks/tenka1_2013_qualB_c 高橋君のいたずらによりバラバラにされた天下一プログラマーコンテストのポスターを見て触発されたショウヘイ君は、天下一プログラマーコンテストのポスターを下図のように$ N\ \times\ M $ のピースに分割したパズルを作ることにした。 draw_puzzle("c0", 3, 3, [ "01", "00", "11", ],[ "101", "010", ]); 上下左右に隣り合うピースの一辺は一方が凸に他方が凹になっており、外周の辺は直線になっている。このとき、一辺が直線で、残り三辺が凹になっているピースを「特殊なピース」とし、これを可能な限り多くなるように配置した時の「特殊なピース」の個数を答えよ。 ただし、四辺が凹のピースは $ A $ 個以上、四辺が凸のピースは $ B $ 個以下にするという条件が与えられる。 入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A $ $ B $ - パズルの縦幅 $ N $、横幅 $ M $ ( $ 2\ \leq\ N,\ M\ \leq\ 8 $ ) 、四辺が凹のピースの数の下限 $ A $ ( $ A\ \geq\ 0 $ ) 、 四辺が凸のピースの数の上限 $ B $ ( $ B\ \geq\ 0 $ ) が、スペースで区切られて、それぞれ整数で与えられる。 - $ A\ +\ B\ \leq\ (N-2)\ \times\ (M-2) $ - 少なくとも $ 1 $ 通りは条件を満たす分割方法が存在する。 - $ A\ =\ 0 $, $ B\ =\ (N-2)\ \times\ (M-2) $ の入力に正解すると、120 点満点に対して部分点として、30 点が与えられる。 - $ M,\ N\ \leq\ 4 $ の入力に正解すると、120 点満点に対して部分点として 40 点が与えられる。 「特殊なピース」の数の最大値を標準出力に $ 1 $ 行で出力せよ。 なお、行の終端には改行が必要である。 ``` 3 3 0 1 ``` ``` 4 ``` ``` 3 4 1 1 ``` ``` 3 ```

N/A

N/A