Icebreaking

$9 \times 9$ 크기의 얼음판 위에서 두 플레이어가 얼음 부수기 게임을 진행합니다.

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

각 칸은 빈 얼음, 구멍 #, 선공이 차지한 칸 a, 후공이 차지한 칸 b 중 하나의 상태를 가집니다. 빈 얼음만 선택할 수 있으며, 구멍과 이미 한 플레이어가 차지한 칸은 다시 선택할 수 없습니다.

얼음판에는 정확히 $9$개의 구멍이 있습니다. 구멍의 위치는 경기마다 주어지는 seed에 따라 결정되며, 서로 다른 칸에 배치됩니다. 두 플레이어는 게임 시작 전에 동일한 얼음판을 입력받습니다.

구멍을 제외한 $72$개의 빈 얼음에는 각각 $-2$, $-1$, $0$, $1$, $2$ 중 하나의 점수가 적혀 있습니다. 얼음의 점수도 seed에 따라 결정됩니다. 음수 점수의 얼음을 차지하면 총점이 감소할 수 있습니다.

게임은 선공 A부터 시작하여 A와 B가 번갈아 턴을 진행합니다. 자신의 턴에는 현재 비어 있는 얼음 칸 $(r,c)$ 하나를 선택합니다.

플레이어가 빈 얼음을 선택하면 다음 과정이 순서대로 진행됩니다.

• 선택한 칸을 현재 플레이어가 차지하고, 그 칸에 적힌 점수를 얻습니다.
• 선택 직전에 해당 칸이 속해 있던 빈 얼음의 상하좌우 연결 영역을 확인합니다.
• 선택한 칸이 사라지면서 연결 영역이 둘 이상으로 나뉘었다면, 각 연결 요소의 크기를 비교합니다.

• 크기가 가장 큰 연결 요소들은 그대로 남고, 그보다 작은 연결 요소들은 모두 현재 플레이어의 칸으로 바뀝니다. 이를 연쇄 점령이라고 합니다.

• 연쇄 점령한 모든 칸에 적힌 점수를 현재 플레이어의 총점에 더합니다.

빈 얼음의 연결 여부는 상하좌우 네 방향만 사용하여 판단합니다. 대각선으로 맞닿은 칸은 연결되지 않습니다. 구멍과 이미 차지한 칸은 빈 얼음의 연결 영역에 포함되지 않습니다.

크기가 가장 큰 연결 요소가 여러 개라면 해당 연결 요소들은 모두 남습니다. 나뉜 모든 연결 요소의 크기가 같다면 연쇄 점령되는 칸은 없습니다.

예를 들어, 하나의 빈 얼음 영역이 크기 $12$, $5$, $5$인 세 영역으로 나뉘면 크기 $5$인 두 영역을 모두 연쇄 점령합니다. 크기 $7$, $7$, $3$인 세 영역으로 나뉘면 크기 $3$인 영역만 연쇄 점령합니다.

다음 행동은 잘못된 행동입니다.

• 출력 형식에 맞지 않는 문자열을 출력하는 경우
• 얼음판의 범위를 벗어난 좌표를 출력하는 경우
• 구멍이나 이미 차지한 칸을 선택하는 경우

잘못된 행동을 한 플레이어는 즉시 패배합니다. 잘못된 행동은 얼음판과 점수에 반영되지 않으며, 상대에게 다음 턴이 주어지지 않습니다. 제한 시간 안에 출력하지 못하거나 프로그램 실행 중 오류가 발생한 경우에도 해당 플레이어가 즉시 패배합니다.

두 플레이어는 서로 독립적인 총 $5{,}000\text{ms}$를 하나씩 가집니다. 게임 준비 응답과 자신의 모든 턴 응답 시간이 자신의 총 시간에서 누적 차감되며, 매 턴 별도의 고정 시간 제한은 없습니다. 한 플레이어가 시간을 사용해도 상대의 남은 시간은 줄어들지 않습니다. 프로그램 수명 전체의 누적 CPU 시간도 플레이어마다 $5{,}000\text{ms}$로 제한됩니다.

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

• 선택 가능한 빈 얼음이 모두 사라졌을 때
• 총 $81$턴이 진행되었을 때
• 한 플레이어가 잘못된 행동을 했을 때
• 한 플레이어에게 시간 초과 또는 실행 오류가 발생했을 때

정상적으로 게임이 종료되면 총점이 더 높은 플레이어가 승리하며, 두 플레이어의 총점이 같다면 무승부입니다.

얼음판의 연결 구조와 각 칸의 점수를 함께 고려하여 최종 승자가 되기 위한 AI를 설계해주세요!

게임을 시작하기 전에 채점기는 두 플레이어에게 동일한 초기 얼음판을 다음의 $9$줄로 입력합니다.

cell_0,0 cell_0,1 ... cell_0,8
...
cell_8,0 cell_8,1 ... cell_8,8

각 줄에는 해당 행의 $9$개 칸이 공백으로 구분되어 주어집니다.

• $(r,c)$가 얼음 칸이면 cell_r,c에는 그 칸의 점수인 -2, -1, 0, 1, 2 중 하나가 주어집니다.
• $(r,c)$가 구멍이면 cell_r,c에는 #이 주어집니다.
• 전체 $81$개 token 중 #은 정확히 $9$개이며, 나머지 $72$개 token은 얼음의 점수입니다.
• 구멍의 위치와 얼음의 점수는 경기의 seed에 따라 결정됩니다. 두 플레이어에게는 항상 같은 초기 얼음판이 주어집니다.

초기 상태 입력이 끝나면 명령 교환을 시작합니다.

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

• r, c, my_time, opp_time, time은 정수입니다.
• r, c는 $0$ 이상 $8$ 이하이며, 각각 행과 열을 의미합니다.
• my_time, opp_time, time은 밀리초(millisecond) 단위로 주어집니다.
• 두 플레이어는 서로 독립적인 총 $5{,}000\text{ms}$를 하나씩 가집니다. 한 플레이어가 사용한 시간은 상대의 남은 시간을 줄이지 않습니다.
• READY와 자신의 모든 TURN 응답 시간이 자신의 총 시간에서 누적 차감됩니다. 매 턴 별도의 고정 시간 제한은 없습니다.
• 프로그램 수명 전체의 누적 CPU 시간도 플레이어마다 $5{,}000\text{ms}$로 제한됩니다. 시작 처리, 상대 턴의 background 계산, 자식 프로세스 계산도 이 CPU 총량에 포함됩니다.
• 자신의 MOVE와 상대의 OPP를 같은 게임 규칙으로 적용하여 프로그램 내부의 얼음판과 점수를 갱신해야 합니다.
• OPP로 주어지는 r, c는 항상 상대가 직전에 선택한 합법적인 좌표입니다.
• 모든 출력 후에는 개행문자를 출력한 뒤 버퍼를 flush해야 합니다.
• 디버그 메시지는 표준 오류에만 출력해야 하며, 표준 출력에는 프로토콜 응답 외의 문자열을 출력하면 안 됩니다.
• 남은 총 시간 안에 응답하지 못하거나 누적 CPU 총량을 사용하면 시간 초과(TLE) 판정을 받습니다.
• 출력 형식에 맞지 않는 문자열을 출력하거나, TURN 명령어가 주어질 때 합법적이지 않은 좌표를 출력하면 잘못된 행동으로 처리되어 즉시 패배합니다. 잘못된 행동 뒤에는 상대에게 OPP 또는 다음 TURN이 전달되지 않습니다.

초기 얼음판 $9$줄을 입력받은 뒤 다음과 같이 통신할 수 있습니다. 아래 표에서는 초기 $9$줄을 생략합니다.

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