#435. [CZOI2019 E] 泡泡棋

    ID: 435 传统题 1000ms 256MiB 尝试: 36 已通过: 5 普及/提高- 上传者: 标签>时间2019来源常州小学生市赛算法基础模拟

[CZOI2019 E] 泡泡棋

题目描述

小 X 备完课后觉得肚子有点饿,就打开 QQ 游戏,先下了局中国象棋,轻松获胜后心情大畅,又玩了会泡泡棋。这个游戏在一个充满五彩缤纷的泡泡的长方形板上进行,在每个回合,玩家选择一组相同颜色的泡泡(玩家只需用鼠标点击这组泡泡中的任意一个即可),之后这些被选中的泡泡就从板上消失了。那些不再被支撑着的气泡便会掉落。如果存在一个空行或空列,那么这个空行或空列将会被移除。如下图所示:用鼠标点击黑色边框框起来的 $7{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{} $ 个黑色泡泡中的任意一个,则框起来的 $7{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}$ 个黑色泡泡就会消失变成第二个图的样子,那些不再被支撑着的黑框中的气泡便会掉落,形成第三个图,第三个图有一个空列,移除这个空列后形成了最终的结果。

每一步的得分是被移除的泡泡的个数的平方。在上面的例子中,这一步的得分为 4949

输入格式

第一行包含两个整数 m,nm,n,表示长方形板的行数和列数。 接下来 mm 行每行包含一个长度为 nn 的由 090 \sim 9 构成的字符串,其中 191 \sim 9 每个数字表示一种颜色的泡泡,00 表示空白方格,即该方格没有泡泡。 最后一行包含两个整数 rowrowcolcol,表示鼠标点击的位置。位置用行和列表示,行从上往下编号,列从左向右编号,上图初始状态的第一行第一列即左上角的位置为空白方格,第一行第二列有一个白色泡泡,第二行第三列有一个灰色泡泡,第四行第五列有一个黑色泡泡。

输出格式

第一行输出得分。 紧接着的 mm 行输出方案,每行连续输出 nn 个数字,没有泡泡的地方用 00 表示。

3 5
31233
12211
33233
2 3
16
30330
11110
33330
4 6
012312
312332
223321
231332
1 4
49
010020
312020
222110
231220

数据范围

1n,m3001 \le n,m \le 300