Table of Contents

ExplanationImplementation

Official Analysis (C++)

Explanation

We can use BFS to perform a floodfill, starting from an unvisited cell, to explore connected regions of the same color. During the floodfill, we collect all the cells in the same connected region by visiting neighbors that share the same color.

To identify regions that can be removed, we calculate the size of each connected region. If the size is greater than or equal to the threshold kk, the region is marked as removable.

After identifying all removable regions, we set the cells in these regions to '0', effectively "removing" them from the grid. To simulate gravity, we let the non-empty cells in each column fall to the lowest available position by swapping them with empty cells ('0').

This process is repeated until no removable regions remain, at which point we output the final state of the grid.

Implementation

Time Complexity: O(N2)\mathcal{O}(N^2)

C++

#include <bits/stdc++.h>
using namespace std;


const int MAX_COLS = 10;
// Movement directions (up, down, left, right)
const vector<pair<int, int>> MOVES = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};


vector<pair<int, int>> find_region(const vector<string> &grid, int row, int col) {
	const int n = grid.size();          // Shorthand for the number of rows
	const char color = grid[row][col];  // Color of the starting cell

Java

import java.io.*;
import java.util.*;


public class MooyoMooyo {
	static final int MAX_COLS = 10;
	// Movement directions
	static final int[][] MOVES = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};


	static List<int[]> findRegion(char[][] grid, int row, int col) {
		int n = grid.length;          // Number of rows

Python

from collections import deque
from typing import List, Tuple


MAX_COLS = 10
# Movement directions (up, down, left, right)
MOVES = [
	(1, 0),
	(-1, 0),
	(0, 1),
	(0, -1),

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum