RiseOJ – 무요 무요

설명

농부 존의 농장에 사는 소들은 손(아니, 발굽)에 남는 시간이 많아서, 비디오 게임을 하며 시간을 보내는 일이 많다. 소들이 가장 좋아하는 게임 중 하나는 뿌요 뿌요라는 인기 있는 인간 비디오 게임을 바탕으로 한 것인데, 소 버전의 이름은 당연히 무요 무요이다.

무요 무요 게임은 세로 $$N$$ 칸 ( $1 \leq N \leq 100$ ), 가로 10칸의 길고 좁은 격자에서 진행된다. 다음은 $$N = 6$$ 인 예시이다.

각 칸은 비어 있거나 (0으로 표시), 아홉 가지 색 중 하나의 건초 더미이다 (문자 1..9로 표시). 중력 때문에 건초 더미는 아래로 떨어지므로, 건초 더미 아래에 0인 칸이 있는 경우는 없다.

두 칸이 가로 또는 세로로 직접 인접해 있고 0이 아닌 같은 색을 가지면, 두 칸은 같은 연결 영역에 속한다. 칸이 $$K$$ 개 이상인 연결 영역이 존재하면, 그 영역의 건초 더미들은 모두 사라져 0이 된다. 그런 연결 영역이 동시에 여러 개 존재하면 모두 동시에 사라진다. 그 후, 중력에 의해 건초 더미들이 아래로 떨어져 0이 된 칸들 중 일부를 채울 수 있다. 그 결과 상태에서 다시 크기가 $$K$$ 칸 이상인 연결 영역이 생길 수 있다. 그렇다면 그 영역들도 사라지고 (그런 영역이 여러 개면 동시에), 중력이 남은 칸들을 아래로 끌어내리며, 크기가 $$K$$ 칸 이상인 연결 영역이 없어질 때까지 이 과정이 반복된다.

무요 무요 보드의 상태가 주어질 때, 이 연산들이 모두 일어난 후 보드의 최종 모습을 출력하여라.

출제자: Brian Dean

제약

출제자: Brian Dean

입력 형식

입력의 첫째 줄에 $$N$$ 과 $$K$$ 가 주어진다 ( $1 \leq K \leq 10N$ ). 나머지 $$N$$ 개의 줄에 보드의 초기 상태가 주어진다.

출력 형식

최종 보드 상태의 그림을 $$N$$ 개의 줄로 출력한다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 mooyomooyo.in · 출력을 쓸 파일 mooyomooyo.out

예제 1

입력

출력

설명

In the example above, if $$K = 3$$ , then there is a connected region of size at
least $$K$$ with color 1 and also one with color 2. Once these are simultaneously
removed, the board temporarily looks like this:

Then, gravity takes effect and the haybales drop to this configuration:

Again, there is a region of size at least $$K$$ (with color 3). Removing it
yields the final board configuration:

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2018-2019 > December > Silver

올림피아드 > USACO > 2018-2019 > December > Silver

태그

JudgeUSACO

무요 무요

평가 및 의견

풀이 제출