最高分数:$300$ 积分
第 $i$ 行、第 $j$ 列的一块石头被放置在每个单元格中,上面刻有数字(1 到 9 之一)。
您可以擦除板上的 1 个单元格。
游戏流程如下:
问题陈述
我们正在玩拼图游戏。此拼图中使用了一块直立的板,其单元格为 $H$ 行 x $W$ 列。第 $i$ 行、第 $j$ 列的一块石头被放置在每个单元格中,上面刻有数字(1 到 9 之一)。
您可以擦除板上的 1 个单元格。
游戏流程如下:
- 当水平相邻单元格中的 $K$ 或更多宝石刻有相同数字时,宝石将会消失。所有这些石头群的消失都是同时发生的。
- 当石头位于空单元格上方的单元格中时,这些石头会落下,从而填充空单元格。
- 所有石子掉落完成后,如果一组或多组石子满足消失条件,则返回步骤1重复。
- 得分为 $\sum_i 2^i \times \left(\text{第 $i$ 链中消失的石子的数字总和(0 索引)}\right)$。
输入
输入由以下格式的标准输入给出。$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}$
输出
- 如果他删除了最佳位置,请输出总分。
约束
- $2 \le H, W \le 30$
- $2 \le K \le 3$
- $答案 \le 1,000,000,000$
- $c_{i,j} ≠ c_{i,j+1} (1 \le j \le W-1)$
子任务
子任务 1 [ $120$ 点 ]- $H, W \le 10$
- $W=K$
- 没有其他限制。
示例输入 1
4 4 2 3413 4121 1424 2312
示例输出 1
23如果删除单元格(4,3):
擦除的最佳位置是单元格(3,2)。
示例输入 2
4 4 2 1212 2121 1212 2121
示例输出 2
54
示例输入 3
7 7 2 8989898 9898989 8989898 9898989 8989898 9898989 8989898
示例输出 3
2520
示例输入 4
17 17 2 12345678912345678 23456789123456789 34567891234567891 45678912345678912 56789123456789123 67891234567891234 78912345678912345 89123456789123456 91234567891234567 12345678912345678 23456789123456789 34567891234567891 45678912345678912 56789123456789123 67891234567891234 78912345678912345 89123456789123456
示例输出 4
2354638