時間制限:$1.0sec$ / メモリ制限:$1024MB$ / tester:square1001 kotamanegi
E869120 君は、以下のようなグリッドを作りました。
さて、E869120 君はグリッドを作っただけではつまらないので、グリッドに「得点」という概念を付けることにしました。
「得点」は、以下のように計算されます。
例えば、以下のグリッドにおける「得点」は以下のようになります。
==================
| | +1 | x2 |
==================
| x2 | 壁 | x2 |
==================
| | | +1 |
==================
####13:29修正 黒いマス -> 壁のマス
マス (1, 1) から (3, 3) に進む方法は 2 通りあり、それぞれの「ポイント」の値は?
(1, 1) -> (1, 2) -> (1, 3) -> (2, 3) -> (3, 3) : ポイントの値は (1, 1) の時点で 1, (1, 2) の時点で +1 されるので 2, (1, 3) の時点で x2 されるので 4, (2, 3) の時点で x2 されるので 8, (3, 3) の時点で +1 されるので 9 となります。
(1, 1) -> (2, 1) -> (3, 1) -> (3, 2) -> (3, 3) : ポイントの値は (1, 1) の時点で 1, (2, 1) の時点で x2 されるので 2, (3, 1) の時点では変わらず 2, (3, 2) の時点では変わらず 2, (3, 3) の時点で +1 されるので 3 となります。
2 つのルートのポイントは 9, 3 なので、「得点」の値は 9 + 3 = 12 となります。
「得点」の値がちょうど N となるようなグリッドを 1 つ構成してください。 ただし、構成するグリッドの H, W の値によって、得点が変わります。
小課題 1 [80 点]
小課題 2 [920 点]
入力は以下の形式で標準入力から与えられる。
N
H W
c[1][1] c[1][2] c[1][3] ... c[1][W]
c[2][1] c[2][2] c[2][3] ... c[2][W]
c[3][1] c[3][2] c[3][3] ... c[3][W]
...
c[H][1] c[H][2] c[H][3] ... c[H][W]
それぞれのマスについて、
ただし、空白区切りではない。
12
3 3
.12
2#2
..1
192
3 3
222
222
222