시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 (추가 시간 없음) | 1024 MB | 75 | 21 | 17 | 32.075% |
이세계로 떨어져 슬라임 연구를 하던 ntopia를 기억하는가? 그는 슬라임 연구를 성공적으로 끝마치고 지구로 돌아갈 수 있게 되었다. 하지만 ntopia의 직업은 사실 슬라임 연구자가 아니었다. 그는 슬라임을 지구로 몰래 들여가 비싼 값에 팔 속셈으로 슬라임 연구자로 위장하고 이세계에 들어온 슬라임 밀수업자였다!
이세계의 슬라임은 빨간색, 파란색, 노란색의 세 가지 종류가 있다. 이들은 서로 다른 색의 두 슬라임이 합쳐지면 나머지 색의 슬라임 두 마리로 분열하는 성질을 가지고 있다. 예를 들어 빨간색 슬라임과 파란색 슬라임이 합쳐지면 노란색 슬라임 두 마리가 된다. 그러나 같은 색의 슬라임은 서로 합쳐질 수 없다.
ntopia는 격자 모양으로 칸이 나누어진 상자에 한 칸에 한 마리씩 슬라임을 잡아넣었다. ntopia의 의도를 눈치챈 슬라임들은 가치를 떨어뜨리기 위해 서로 합체와 분열을 반복해서 모두 같은 색이 되려고 한다. 그러나 슬라임들은 먼 거리를 점프할 수 없기 때문에 상하좌우로 인접한 칸에 있는 슬라임과만 합쳐질 수 있으며, 분열된 두 슬라임은 다시 원래 각자의 위치로 떨어진다. 게다가 ntopia는 곧 상자를 들고 지구로 출발할 예정이기 때문에 슬라임들에게는 최대 100만 번의 합체를 할 시간밖에 남아 있지 않다.
슬라임들의 배치가 주어질 때 슬라임들이 목표를 달성할 수 있을지 확인해 보자.
첫 줄에 상자의 세로 방향의 칸의 개수와 가로 방향의 칸의 개수를 의미하는 정수 N과 M(1 ≤ N, M ≤ 200)이 주어진다.
다음 N개의 줄에 걸쳐 각 줄에 슬라임들의 배치를 의미하는 M글자의 문자열이 하나씩 주어진다. 문자열은 문자 R
, B
, Y
로만 이루어져 있으며, 각각 빨간색, 파란색, 노란색 슬라임을 의미한다.
슬라임들이 목표를 달성할 수 있다면 첫 줄에 필요한 합체 횟수를 의미하는 정수 K(0 ≤ K ≤ 1,000,000)를 출력한다.
다음 K줄에 걸쳐 각 줄에 합쳐지는 두 슬라임의 위치를 나타내는 네 개의 정수 x1, y1, x2, y2(1 ≤ x1, x2 ≤ N, 1 ≤ y1, y2 ≤ M)를 공백으로 구분하여 출력한다. 이는 x1행 y1열에 있는 슬라임과 x2행 y2열에 있는 슬라임이 합쳐짐을 의미한다.
슬라임들이 목표를 달성할 수 없다면 첫 줄에 -1
을 출력한다.
2 2 RB BY
4 1 1 1 2 1 1 2 1 1 1 1 2 2 1 2 2
1 3 RRB
-1
University > 서울대학교 > 2019 서울대학교 프로그래밍 경시대회 > Division 1 A번