← 返回题目列表

AtCoder · s8pc_3_b

B. 落石游戏

中文机器翻译题面 查看原题
最高分数:$300$ 积分

问题陈述

我们正在玩拼图游戏。此拼图中使用了一块直立的板,其单元格为 $H$ 行 x $W$ 列。
第 $i$ 行、第 $j$ 列的一块石头被放置在每个单元格中,上面刻有数字(1 到 9 之一)。
您可以擦除板上的 1 个单元格。

游戏流程如下:
  1. 当水平相邻单元格中的 $K$ 或更多宝石刻有相同数字时,宝石将会消失。所有这些石头群的消失都是同时发生的。
  2. 当石头位于空单元格上方的单元格中时,这些石头会落下,从而填充空单元格。
  3. 所有石子掉落完成后,如果一组或多组石子满足消失条件,则返回步骤1重复。
  4. 得分为 $\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$
子任务 2 [ $180$ 点 ]
  • 没有其他限制。

示例输入 1

4 4 2
3413
4121
1424
2312

示例输出 1

23
如果删除单元格(4,3):

总分:$7 + 16 = 23$分。
擦除的最佳位置是单元格(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
作者:E869120