Hanpang

Hanpang은 $15 \times 8$ 크기의 보드에서 같은 색 타일을 한꺼번에 제거하며 높은 점수를 얻는 1인용 게임입니다.

1. 보드와 타일

보드는 $1 \times 1$ 크기의 칸이 $15$행 $8$열로 배열된 형태입니다. 행 번호는 위에서 아래로 $1$행부터 $15$행, 열 번호는 왼쪽에서 오른쪽으로 $1$열부터 $8$열까지이며, $r$행 $c$열의 칸을 $(r,c)$로 표기합니다.

각 칸은 빈칸이거나 세 가지 색 중 하나의 타일을 가집니다. 새로 만들어지는 타일의 색은 세 가지 색 중 하나를 서로 독립적으로 같은 확률로 선택하여 정합니다.

게임을 시작할 때 보드는 비어 있으며, 맨 아래에 새 타일 $8$개로 이루어진 행 하나가 추가됩니다.

2. 게임 진행

한 턴에는 비어 있지 않은 칸 $(r,c)$ 하나를 선택합니다. 선택한 타일과 상하좌우로 연결된 같은 색 타일을 모두 제거합니다. 대각선으로 맞닿은 타일은 연결되지 않으며, 연결된 타일이 하나뿐인 경우에도 선택할 수 있습니다.

한 번에 $k$개의 타일을 제거했다면 $k^2$점을 얻습니다. 타일을 제거한 뒤에는 각 열의 남은 타일이 빈칸 없이 아래로 떨어집니다.

이후 새 타일 $8$개로 이루어진 행이 보드의 맨 아래에 추가되고, 기존 보드는 한 행 위로 이동합니다. 이 과정을 한 턴으로 합니다.

3. 게임 종료와 점수

게임은 다음 조건 중 하나가 만족되면 종료됩니다.

• 새 행을 추가하면서 보드의 맨 위에 남아 있던 타일이 보드 밖으로 밀려난 경우
• $200$턴을 진행한 경우

게임을 종료시킨 마지막 행동에서 얻은 점수도 최종 점수에 포함됩니다. 게임이 종료될 때까지 얻은 점수의 합이 최종 점수입니다.

새로운 행이 계속 추가되는 상황을 고려하여 큰 연결 요소를 만들고 높은 점수를 얻는 AI를 설계해주세요!

채점기는 다음의 한 줄 단위로 플레이어와 통신합니다.

• remaining_ms, row, col은 정수입니다.
• remaining_ms는 플레이어에게 남은 시간을 밀리초 단위로 나타냅니다.
• new_row는 길이가 $8$인 문자열이며, 각 문자는 타일의 색을 나타내는 1, 2, 3 중 하나입니다. 첫 번째 TURN에서 주어지는 new_row도 보드의 맨 아래 행에 추가됩니다.
• row는 $1$ 이상 $15$ 이하, col은 $1$ 이상 $8$ 이하이며, 각각 위에서부터 센 행과 왼쪽에서부터 센 열을 의미합니다.
• PANG row col로 선택한 칸에는 타일이 있어야 합니다. 연결 요소의 크기가 $1$인 타일도 선택할 수 있습니다.
• 플레이어는 START 응답과 모든 TURN 응답을 합해 총 $5{,}000\text{ms}$를 사용할 수 있습니다.
• 모든 출력 후에는 개행문자를 출력한 뒤 버퍼를 flush해야 합니다.
• 남은 시간 안에 응답하지 못하면 게임이 종료되며, 마지막으로 확정된 점수를 최종 점수로 사용합니다.
• 출력 형식에 맞지 않는 문자열이나 올바르지 않은 좌표를 출력한 경우에도 게임이 종료되며, 해당 행동 직전까지 확정된 점수를 최종 점수로 사용합니다.
• 게임이 끝나면 채점기는 추가 명령을 보내지 않고 플레이어의 프로그램을 종료합니다.

다음은 플레이어와 채점기가 통신하는 예시입니다. 시간 값은 설명을 위한 예시입니다.

• PYTHON3, PYPY3 : main.py
• CPP20 : main.cpp