2018 Dec Silver Problem 3 Mooyo Mooyo

Official Problem Statement

Mooyo Mooyo

Problem

The problem presents a 2D game grid which is N x 10 (N≤100) squares, each square either contains a cow or is empty. Adjacent squares sharing an edge (not only a corner) with the same number are part of the same component. If a component contains at least K squares (K≤N), it's removed from the grid, and all cows above it in the same column fall down to take the places of the cows in the removed component, potentially forming new components. This process continues until no component contains K or more squares.

The task is to simulate this process and output the final state of the board.

Input

The first line of input contains two integers N and K (1≤N≤100). The next N lines contain 10 digits each, specifying the initial state of the grid.

Output

The output should be N lines, each containing 10 digits, showing the final state of the game board.

Solution

The problem can be solved with a depth-first search algorithm.

• Perform a depth-first search (DFS) on every cell to find components, and mark all cells in a component with a same special value.
• Iterate through each cell. If its value is the special value and its component size is greater or equal to K, mark it as '0'.
• Then the gravity step is done by repeatedly going through each column from bottom to top and moving any '0' cell down if it is not at the bottom and the cell below it is non-'0'.
• Repeat steps 1-3 until there are no more components of size K or larger.

The overall complexity of this solution is O(N^3), which is fast enough given the constraints.

Code

C++

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

int N, M;
vector<string> board;

void dfsCount(int i, int j, char val, int& count, vector<vector<bool>>& visited) {
	if (i < 0 || j < 0 || i >= N || j >= M || board[i][j] != val || visited[i][j]) 
		return;
	count++;
	visited[i][j] = true;
	dfsCount(i - 1, j, val, count, visited);
	dfsCount(i + 1, j, val, count, visited);
	dfsCount(i, j - 1, val, count, visited);
	dfsCount(i, j + 1, val, count, visited);
}

void dfsMark(int i, int j, char val, vector<vector<bool>>& visited) {
	if (i < 0 || j < 0 || i >= N || j >= M || board[i][j] != val) 
		return;
	board[i][j] = '0';
	dfsMark(i - 1, j, val, visited);
	dfsMark(i + 1, j, val, visited);
	dfsMark(i, j - 1, val, visited);
	dfsMark(i, j + 1, val, visited);
}

void applyGravity() {
	for (int j = 0; j < M; ++j) {
		int writeIndex = N - 1;
		for (int i = N - 1; i >= 0; --i) {
			if (board[i][j] != '0') {
				board[writeIndex][j] = board[i][j];
				writeIndex--;
			}
		}
		while (writeIndex >= 0) 
			board[writeIndex--][j] = '0';
	}
}

bool simulate() {
	bool progress = false;
	vector<vector<bool>> visited(N, vector<bool>(M, false));
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
 			if (!visited[i][j] && board[i][j] != '0') {
				int count = 0;
				dfsCount(i, j, board[i][j], count, visited);
				if (count >= M) {
					progress = true;
					dfsMark(i, j, board[i][j], visited);
				}
			}
		}
	}
	if (progress) 
		applyGravity();
	return progress;
}

int main() {
	freopen("mooyomooyo.in", "r", stdin);
	freopen("mooyomooyo.out", "w", stdout);

	cin >> N >> M;
	board.resize(N);
	for (int i = 0; i < N; ++i)
		cin >> board[i];

	while(simulate());

	for (const auto& row : board)
		cout << row << endl;
	return 0;
}

Java

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

public class Main {
    static int N, M;
    static char[][] board;

    public static void dfsCount(int i, int j, char val, int[] count, boolean[][] visited) {
        if (i < 0 || j < 0 || i >= N || j >= M || board[i][j] != val || visited[i][j]) 
            return;
        count[0]++;
        visited[i][j] = true;
        dfsCount(i - 1, j, val, count, visited);
        dfsCount(i + 1, j, val, count, visited);
        dfsCount(i, j - 1, val, count, visited);
        dfsCount(i, j + 1, val, count, visited);
    }

    public static void dfsMark(int i, int j, char val, boolean[][] visited) {
        if (i < 0 || j < 0 || i >= N || j >= M || board[i][j] != val) 
            return;
        board[i][j] = '0';
        dfsMark(i - 1, j, val, visited);
        dfsMark(i + 1, j, val, visited);
        dfsMark(i, j - 1, val, visited);
        dfsMark(i, j + 1, val, visited);
    }

    public static void applyGravity() {
        for (int j = 0; j < M; ++j) {
            int writeIndex = N - 1;
            for (int i = N - 1; i >= 0; --i) {
                if (board[i][j] != '0') {
                    board[writeIndex][j] = board[i][j];
                    writeIndex--;
                }
            }
            while (writeIndex >= 0) 
                board[writeIndex--][j] = '0';
        }
    }

    public static boolean simulate() {
        boolean progress = false;
        boolean[][] visited = new boolean[N][M];
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < M; ++j) {
                if (!visited[i][j] && board[i][j] != '0') {
                    int[] count = {0};
                    dfsCount(i, j, board[i][j], count, visited);
                    if (count[0] >= M) {
                        progress = true;
                        dfsMark(i, j, board[i][j], visited);
                    }
                }
            }
        }
        if (progress) 
            applyGravity();
        return progress;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new FileReader("mooyomooyo.in"));
        PrintWriter writer = new PrintWriter(new BufferedWriter(new FileWriter("mooyomooyo.out")));
        StringTokenizer st = new StringTokenizer(reader.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        board = new char[N][M];

        for (int i = 0; i < N; ++i) {
            board[i] = reader.readLine().toCharArray();
        }

        while(simulate());

        for (char[] row : board) {
            writer.println(new String(row));
        }

        writer.close();
        reader.close();
    }
}

Python

from sys import stdin, stdout

N, M = map(int, stdin.readline().split())
board = [list(stdin.readline().strip()) for _ in range(N)]

def dfs_count(i, j, val, visited):
    if i < 0 or j < 0 or i >= N or j >= M or board[i][j] != val or visited[i][j]:
        return 0
    visited[i][j] = True
    return 1 + dfs_count(i - 1, j, val, visited) + dfs_count(i + 1, j, val, visited) \
           + dfs_count(i, j - 1, val, visited) + dfs_count(i, j + 1, val, visited)

def dfs_mark(i, j, val):
    if i < 0 or j < 0 or i >= N or j >= M or board[i][j] != val:
        return
    board[i][j] = '0'
    dfs_mark(i - 1, j, val)
    dfs_mark(i + 1, j, val)
    dfs_mark(i, j - 1, val)
    dfs_mark(i, j + 1, val)

def apply_gravity():
    for j in range(M):
        empty = [row[j] == '0' for row in board]
        write_index = N - 1
        for i in range(N - 1, -1, -1):
            if not empty[i]:
                board[write_index][j] = board[i][j]
                write_index -= 1
        for i in range(write_index, -1, -1):
            board[i][j] = '0'

def simulate():
    progress = False
    visited = [[False] * M for _ in range(N)]
    for i in range(N):
        for j in range(M):
            if not visited[i][j] and board[i][j] != '0':
                count = dfs_count(i, j, board[i][j], visited)
                if count >= M:
                    progress = True
                    dfs_mark(i, j, board[i][j])
    if progress:
        apply_gravity()
    return progress

while simulate():
    pass

for row in board:
    stdout.write("".join(row) + "\n")