B - Falling Stone Game

Contest Duration: 2016-11-20 20:15:00+0900 - 2016-11-20 23:15:00+0900 (local time) (180 minutes)

B - Falling Stone Game Editorial

Time Limit: 1 sec / Memory Limit: 256 MB

Max Score: $300$ Points

Problem Statement

We are playing a puzzle. An upright board with $H$ rows by $W$ columns of cells, is used in this puzzle.
A stone in $i$-th row and $j$-th column engraved with a digit, one of 1 through 9, is placed in each of the cells.
You can erase 1 cell in the board.

The game process is following:

When $K$ or more stones in horizontally adjacent cells are engraved with the same digit, the stones will disappear. Disappearances of all such groups of stones take place simultaneously.
When stones are in the cells above the emptied cells, these stones drop down so that the emptied cells are filled.
After the completion of all stone drops, if one or more groups of stones satisfy the disappearance condition, repeat by returning to the step 1.
Score is $\sum_i 2^i \times \left(\text{Sum of numbers in the stones which disappeared in the $i$-th chain (0-indexed)}\right)$.

Please answer the points if he erased the optimal place.

Input

The input is given from standard input in the following format.

$H \ W \ K$ $c_{1, 1} \ c_{1, 2} \ \cdots \ c_{1, W}$ $c_{2, 1} \ c_{2, 2} \ \cdots \ c_{2, W}$ $\vdots \ \ \ \ \ \ \ \ \ \ \vdots \ \ \ \ \ \ \ \ \ \ \vdots$ $c_{H, 1} \ c_{H, 2} \ \cdots \ c_{H, W}$

Output

Please output total points if he erase the optimal place.

Constraints

$2 \le H, W \le 30$
$2 \le K \le 3$
$answer \le 1,000,000,000$
$c_{i,j} ≠ c_{i,j+1} (1 \le j \le W-1)$

Subtasks

Subtask 1 [ $120$ points ]

$H, W \le 10$
$W=K$

Subtask 2 [ $180$ points ]

There are no additional constraints.

Sample Input 1

Sample Output 1

If you erase cell(4,3):

Total score: $7 + 16 = 23$points.
The optimal place to erase is cell(3,2).

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

Sample Input 4

17 17 2
12345678912345678
23456789123456789
34567891234567891
45678912345678912
56789123456789123
67891234567891234
78912345678912345
89123456789123456
91234567891234567
12345678912345678
23456789123456789
34567891234567891
45678912345678912
56789123456789123
67891234567891234
78912345678912345
89123456789123456

Sample Output 4

writer: E869120

配点： $300$ 点

問題文

square1001氏は、パソコン部に入るために試験を受けました。
この試験の内容は、以下のようなものであります。

$H \times W$ の盤面が与えられる。
その盤面の各マスは、 $1 \sim 9$ の数字が書かれている。また、1行目が一番上である。
あなたは、セルのうち1つのマスを消すことができる。消した上のマスは落ちてくる。

また、そのゲームは以下のようなステップで進行する。

1:$K$ 個以上の水平に隣り合うセルに同じ数字を彫った石があれば，これらの石は消滅する．こうした石群の消滅はすべて同時に起きる。
2:石が消滅したセルの上方のセルに石があれば，空きを埋めるように石が落下する。
3:すべての石の落下完了後に，消滅の条件を満たすようになった石群があれば，ステップ1に戻って繰り返す。
4:スコアは, $2^i \times \left(i \text{回目の消滅で消えた数字の値の和}\right)$ の合計である。ただし、最初の消滅を0回目とする。

そのとき、square1001氏が最適にやって試験に受かるか調べるために、最適にセルを消したときに何点取れるかを計算することにした。
square1001氏を助けるために、最大の点数を出力しなさい。

入力

入力は以下の形式で標準入力から与えられる。

$H \ W \ K$ $c_{1, 1} \ c_{1, 2} \ \cdots \ c_{1, W}$ $c_{2, 1} \ c_{2, 2} \ \cdots \ c_{2, W}$ $\vdots \ \ \ \ \ \ \ \ \ \ \vdots \ \ \ \ \ \ \ \ \ \ \vdots$ $c_{H, 1} \ c_{H, 2} \ \cdots \ c_{H, W}$

1行目に, 盤面の縦、横の大きさ$H$, $W$と、何個横に並ぶと消滅するかを表す数 $K$ が与えられる。
2行目から, $H$行にわたって盤面の状況が与えられる。
1～9はそれぞれの数字があることを示す。

出力

出力は以下の形式で標準出力に従うこと。

最大の点数を1行に出力しなさい。

制約

$2 \le H, W \le 30$
点数は $1,000,000,000$ 点を超えない
最初の盤面では, すべての横に隣り合うマス同士は同じ数が書かれていることはない。

小課題

小課題1 [ $120$ 点 ]

$H, W \le 10$
$W=K$

小課題2 [ $180$点 ]

追加の制約はない。

入力例1

出力例1

場所 $(4, 3)$ を押すと以下のようになります。

よって, $7+16=23$ 点となる。
また, 場所 $(4,3)$ を消すのが最適である。

入力例2

出力例2

この入力例は小課題1の制約を満たさない。

入力例3

出力例3

この入力例は小課題1の制約を満たさない。

入力例4

17 17 2
12345678912345678
23456789123456789
34567891234567891
45678912345678912
56789123456789123
67891234567891234
78912345678912345
89123456789123456
91234567891234567
12345678912345678
23456789123456789
34567891234567891
45678912345678912
56789123456789123
67891234567891234
78912345678912345
89123456789123456

出力例4

連鎖数が非常に大きくなることもある。

問題作成者:E869120