Mooyo Mooyo

题目描述

由于有大量空闲时间（或者说，蹄子空闲），农夫约翰农场里的奶牛经常通过玩电子游戏来打发时间。它们最喜欢的游戏之一基于人类的一款流行游戏 Puyo Puyo；奶牛版当然叫做 Mooyo Mooyo。

Mooyo Mooyo 游戏在一个高而窄的网格上进行，网格高 $N$ 个格子（$1 \leq N \leq 100$），宽 10 个格子。下面是一个 $N = 6$ 的例子： 0000000000 0000000300 0054000300 1054502230 2211122220 1111111223

每个格子要么为空（用 0 表示），要么是九种不同颜色之一的干草捆（用字符 1..9 表示）。重力会使干草捆向下掉落，因此在任何干草捆的下方都不会出现 0 格子。

如果两个格子在水平方向或垂直方向直接相邻，并且它们具有相同的非零颜色，则它们属于同一个连通区域。只要存在一个至少包含 $K$ 个格子的连通区域，该区域内的所有干草捆都会消失，变为 0。如果同时存在多个这样的连通区域，它们会同时消失。之后，重力可能会使干草捆下落，以填补一些由于消失而变成 0 的格子。

在新的棋盘状态中，可能再次出现大小至少为 $K$ 的连通区域。如果是这样，它们也会消失（若有多个区域则同时消失），然后重力把剩余格子向下拉动，如此反复，直到不存在大小至少为 $K$ 的连通区域为止。

给定一个 Mooyo Mooyo 棋盘的初始状态，请输出经过上述操作后的最终棋盘图像。

输入格式

第一行输入包含 $N$ 和 $K$（$1 \leq K \leq 10N$）。 接下来的 $N$ 行给出棋盘的初始状态。

输出格式

请输出 $N$ 行，描述最终的棋盘状态图像。

6 3
0000000000
0000000300
0054000300
1054502230
2211122220
1111111223

0000000000
0000000000
0000000000
0000000000
1054000000
2254500000

提示

在上面的例子中，如果 $K = 3$，那么存在一个大小至少为 $K$ 的颜色为 1 的连通区域，以及一个颜色为 2 的连通区域。一旦它们同时被移除，棋盘会暂时变成这样： 0000000000 0000000300 0054000300 1054500030 2200000000 0000000003

然后，重力生效，干草捆下落到如下状态： 0000000000 0000000000 0000000000 0000000000 1054000300 2254500333

此时再次出现一个大小至少为 $K$ 的连通区域（颜色为 3）。移除它得到最终棋盘状态： 0000000000 0000000000 0000000000 0000000000 1054000000 2254500000

题目来源：Brian Dean

标签: USACO|2018|Silver

来源

USACO|2018|Silver