(Analysis by Nathan Pinsker )

There are three components to this implementation problem:

• Figuring out which cells should be deleted
• Deleting them
• Applying gravity

Once we have implementations for these, we can simply repeatedly do these things in order until no cells should be deleted, and then output the state.

To figure out which cells should be deleted, we first consider every cell in the array in sequence. We start a flood fill from that cell if the cell is nonempty (and hasn't already been handled by a previous flood fill). We keep track of all points that we touch with the flood fill in an array. If the array's length ends up being larger than $K$, then all those points need to be deleted.

To delete cells, we just replace them in the array with '0'. We can even do this after each flood-fill, and we don't need to wait until we've finished flood-filling all the regions.

Finally, to apply gravity, we can simply count the number of '0' squares in each column (from the bottom going up) until we reach an occupied square. Then, we shift that column down by that number of squares.

Here's Brian's code. Note that he uses a slightly different method of counting how many cells belong to each region: he assigns each region a unique code $\texttt{r}$, and keeps track of each region's size in the array $\texttt{regsizes}$.


#include <iostream>
#include <fstream>
using namespace std;

int N, K, board, region, regsizes;

void gravity(void)
{
for (int j=0; j<10; j++) {
int top = N-1, bottom = N-1;
while (top >= 0) {
while (top >= 0 && board[top][j] == 0) top--;
if (top >= 0)
board[bottom--][j] = board[top--][j];
}
while (bottom >= 0) board[bottom--][j] = 0;
}
}

void visit(int i, int j, int r, int c)
{
if (i<0 || i>=N || j<0 || j>9 || board[i][j]!=c || region[i][j]!=0) return;
region[i][j] = r;
regsizes[r]++;
visit(i-1,j,r,c);
visit(i+1,j,r,c);
visit(i,j-1,r,c);
visit(i,j+1,r,c);
}

bool iterate(void)
{
int r = 1;
for (int i=0; i<N; i++)
for (int j=0; j<10; j++)
region[i][j] = 0;
for (int i=0; i<N; i++)
for (int j=0; j<10; j++)
if (board[i][j] && !region[i][j]) visit(i,j,r++,board[i][j]);
bool progress = false;
for (int i=0; i<N; i++)
for (int j=0; j<10; j++)
if (board[i][j] && regsizes[region[i][j]]>=K) {
board[i][j] = 0;
progress = true;
}
gravity();
while (r) regsizes[r--] = 0;
return progress;
}

int main(void)
{
ifstream fin ("mooyomooyo.in");
fin >> N >> K;
string s;
for (int i=0; i<N; i++) {
fin >> s;
for (int j=0; j<10; j++) board[i][j] = s[j]-'0';
}

while (iterate());

ofstream fout ("mooyomooyo.out");
for (int i=0; i<N; i++) {
for (int j=0; j<10; j++) fout << board[i][j];
fout << "\n";
}
return 0;
}