P5121 [USACO18DEC] Mooyo Mooyo S

Because they have lots of free time on their hands (or more accurately, on their hooves), the cows on Farmer John’s farm often play video games to pass the time. One of their favorite games is a cow-themed version of the popular game Puyo Puyo, naturally called Mooyo Mooyo. Mooyo Mooyo is played on a tall, narrow board with height $N$ ($1\le N\le 100$) and width $10$. Here is an example board with $N=6$: ``` 0000000000 0000000300 0054000300 1054502230 2211122220 1111111223 ``` Each cell is either empty (represented by $0$) or a hay bale of one of nine colors (represented by characters $1\dots 9$). Gravity causes hay bales to fall, so there will be no hay bale with a $0$ directly below it. If two cells are directly adjacent horizontally or vertically and have the same non-$0$ color, then they belong to the same connected component. Whenever a connected component of size at least $K$ appears, all hay bales in that component disappear and become $0$. If multiple such components exist at the same time, they disappear simultaneously. Then gravity may cause hay bales to fall downward into cells that became $0$. In the new layout, there may again be connected components of size at least $K$. If so, they also disappear (simultaneously if there are multiple), and gravity makes the remaining blocks fall again. This process continues until there is no connected component of size at least $K$. Given a Mooyo Mooyo board state, output the final board pattern after all these processes occur.

The first line of input contains $N$ and $K$ ($1\le K\le 10N$). The next $N$ lines give the initial state of the board.

Output $N$ lines describing the final state of the board.

In the example above, if $K=3$, then there is a connected component of color $1$ with size at least $K$, and also a connected component of color $2$. After they are removed simultaneously, the board temporarily becomes: ``` 0000000000 0000000300 0054000300 1054500030 2200000000 0000000003 ``` Then, due to gravity, the hay bales fall and form this layout: ``` 0000000000 0000000000 0000000000 0000000000 1054000300 2254500333 ``` Once again, a connected component of size at least $K$ appears (color $3$). Removing this component gives the final board layout: ``` 0000000000 0000000000 0000000000 0000000000 1054000000 2254500000 ``` Translated by ChatGPT 5