세임 게임

세임(Same)은 10행 15열 판에서 혼자 하는 게임이다. 각 칸에는 빨강(R), 초록(G), 파랑(B) 중 한 색의 공이 하나씩 놓여 있다. 색이 같은 두 공을, 같은 색 공만 밟으면서 상하좌우로 오갈 수 있으면 두 공은 같은 덩어리에 속한다.

한 턴마다 플레이어는 공이 두 개 이상인 덩어리에서 공을 하나 고르고, 그 덩어리의 공을 모두 판에서 없앤다. 그다음 판을 두 단계로 압축한다.

1. 각 열에 남은 공을 아래로 내려 빈칸을 채운다. 열 안에서 공의 순서는 그대로 유지한다.
2. 어떤 열이 비면 그 오른쪽 열을 왼쪽으로 최대한 당겨 붙인다. 열의 순서는 그대로 유지한다.

예를 들어 아래 판에서 왼쪽 아래 끝의 공을 고르면 다음과 같이 변한다.

목표는 판의 공을 모두 없애는 것이다. 공이 하나도 남지 않거나 모든 덩어리의 크기가 1이 되면 게임이 끝난다.

점수는 이렇게 매긴다. 시작 점수는 0이다. 크기가 $m$인 덩어리를 없애면 점수가 $(m-2)^2$만큼 오른다. 게임이 끝났을 때 공이 하나도 남지 않았으면 보너스 1000점을 더한다.

매 턴 가장 큰 덩어리를 주는 공을 고르는 전략이 좋을 것 같아서, 그 전략대로 게임을 진행하는 프로그램을 짜서 확인하려고 한다. 가장 큰 덩어리를 주는 공이 둘 이상이면 그중 가장 왼쪽 공을 고른다. 그래도 여럿이 남으면 그중 가장 아래쪽 공을 고른다.

첫 줄에 게임의 수를 나타내는 양의 정수가 주어진다. 각 게임의 초기 배치는 맨 윗줄부터 아래로 한 줄씩 주어진다. 각 줄은 "R", "G", "B" 중 하나인 문자 15개로 이루어지고, 왼쪽부터 오른쪽까지 공의 색을 나타낸다. 각 게임 앞에는 빈 줄이 하나 놓인다.

각 게임마다 게임 번호를 출력하고, 빈 줄을 하나 출력하고, 각 턴의 정보를 한 줄씩 출력한 뒤, 마지막에 최종 점수를 출력한다.

게임 번호 줄의 형식은 다음과 같다.

Game x:

각 턴은 다음 형식으로 출력한다.

Move x at (r,c): removed b balls of color C, got s points.

• x는 턴 번호이다.
• (r,c)는 고른 공의 행 번호와 열 번호이다. 행은 아래에서부터 1번부터 10번까지, 열은 왼쪽에서부터 1번부터 15번까지 센다.
• b는 없앤 덩어리의 공 개수이다.
• C는 없앤 공의 색으로 "R", "G", "B" 중 하나이다.
• s는 이 턴에서 얻은 점수이다. 이 턴에 공이 모두 사라져도 보너스 1000점은 포함하지 않는다.

최종 점수는 다음 형식으로 출력한다.

Final score: s, with b balls remaining.

s는 보너스까지 더한 최종 점수, b는 판에 남은 공의 개수이다. 개수가 1이어도 "ball"과 "point"의 복수형을 그대로 쓴다. 이어지는 두 게임 사이에는 빈 줄을 하나 출력한다.