마키의 사탕 줍기

휴리카 아카데미의 복도에 사탕이 흩어져 있습니다. 마키는 술래에게 잡히기 전에 사탕을 최대한 많이 모으려 합니다.

복도는 $N$행 $N$열의 미로로 이루어져 있습니다. $N$은 $11$ 이상 $23$ 이하의 정수입니다. 행 번호는 위에서 아래로, 열 번호는 왼쪽에서 오른쪽으로 $1$부터 $N$까지이며, $x$행 $y$열의 칸을 $(x,y)$로 표기합니다.

각 칸은 벽 또는 통로입니다. 가장 바깥쪽 한 줄은 모두 통로이며, 마키와 술래 한 명은 서로 다른 내부 통로에서 시작합니다. 가장 바깥쪽을 제외한 통로의 수를 $F$라고 할 때, 사탕은 $\max(1,\min(F-2,\lfloor 0.2F+0.5\rfloor))$개 있습니다. 처음에는 마키와 술래가 없는 서로 다른 통로에 놓이며, 바깥쪽 통로에도 놓일 수 있습니다.

마키에게는 미로 전체가 보이지 않습니다. 마키가 처음 바라보는 방향은 상하좌우 중 무작위로 정해지며, 다음과 같이 주변을 봅니다.

• 자신의 칸과 정면에서 처음 만나는 벽까지는 지형과 사탕, 술래를 모두 봅니다. 첫 벽을 포함하며, 벽이 없으면 미로 끝까지 봅니다.
• 자신의 바로 왼쪽, 오른쪽, 뒤쪽 칸은 벽인지 통로인지만 압니다. 정면에서 보이는 각 통로 칸의 바로 왼쪽과 오른쪽 칸도 지형만 압니다.
• 첫 벽의 양옆이나 벽 너머는 보이지 않습니다. 옆으로 뻗은 통로를 따라 시야가 꺾이지도 않습니다.

여기서 왼쪽과 오른쪽은 마키가 바라보는 방향을 기준으로 합니다. 아래 그림은 마키가 $(5,5)$에서 위를 바라보는 경우입니다.

마키는 한 번 본 지형과 사탕을 기억합니다. 처음부터 바깥쪽이 통로라는 사실은 알지만, 그곳에 사탕이 있는지는 직접 보아야 합니다. 매 턴 주어지는 지도에는 현재 시야와 지금까지의 기억이 다음 기호로 표시됩니다.

사탕은 마키가 먹기 전까지 이동하거나 사라지지 않습니다. 한 번 확인한 사탕은 시야 밖에서도 C로 표시됩니다. 지형만 본 칸에서는 이전의 사탕 정보를 유지합니다. 술래는 현재 시야에 있을 때만 H 또는 X로 표시됩니다. .은 확인한 통로라는 뜻이며, 시야 밖에서 새로 생긴 사탕이나 술래가 있을 수 있습니다. #과 .만으로 현재 시야에 들어온 칸인지도 구별할 수 없습니다.

마키는 술래의 발소리도 듣습니다. 두 캐릭터 사이에서 벽을 통과하지 않고 상하좌우로 이동하는 최단 거리에 따라 다음 값이 주어집니다. 발소리로는 술래의 방향을 알 수 없습니다.

마키는 자신의 턴에 다음 행동 중 하나를 수행합니다. 모든 행동은 한 턴을 사용합니다.

이동할 칸이 벽이거나 미로 밖이면 방향만 바뀌고 이동하지 않습니다. 이 경우에도 한 턴을 사용합니다. O와 S는 위치와 최종 방향을 바꾸지 않습니다.

O를 수행하면 네 방향을 각각 바라볼 때의 시야를 합쳐 봅니다. 어느 한 방향에서라도 내용까지 보이는 칸은 사탕과 술래까지 확인하며, 나머지 칸은 지형만 확인합니다. 이때 본 내용은 즉시 기억에 반영됩니다. 술래가 움직인 뒤에는 원래 바라보던 방향의 시야만 다시 확인합니다. 다음 입력에는 그때 보이는 술래만 표시됩니다.

한 턴은 다음 순서로 진행됩니다.

1. 마키가 행동합니다. 사탕이 있는 칸에 도착하면 사탕을 먹고 $1$점을 얻습니다.
2. 먹은 사탕은 마키, 술래, 다른 사탕이 없는 다른 통로에 즉시 다시 놓입니다. 바깥쪽 통로에도 놓일 수 있으며 사탕의 총수는 유지됩니다.
3. 마키의 행동 직후 시야를 기억에 반영합니다. 마키와 술래가 같은 칸에 있으면 잡히며 게임이 끝납니다.
4. 술래가 홀수 번째 턴에는 한 번, 짝수 번째 턴에는 두 번 행동합니다. 각 행동 직후 두 캐릭터가 같은 칸에 있으면 즉시 게임이 끝납니다.
5. 게임이 끝나지 않았다면 마키의 일반 시야와 발소리를 갱신하고 다음 턴으로 넘어갑니다.

술래도 상하좌우 이동, 둘러보기, 기다리기를 사용합니다.

술래는 사탕을 먹지 않으며 사탕이 있는 칸에 설 수 있습니다. 마키가 술래와 사탕이 함께 있는 칸으로 이동하면 사탕 점수를 얻은 뒤 잡힙니다. 같은 칸에 있는 즉시 잡히므로 두 캐릭터가 서로 통과하거나 자리를 바꿀 수는 없습니다.

게임은 마키가 잡히거나 $100$번째 턴의 술래 행동이 끝나면 종료됩니다. 한 판의 점수는 먹은 사탕의 수입니다. 잡혀도 이미 얻은 점수는 유지됩니다.

술래를 피해 사탕을 최대한 많이 모으는 마키의 AI를 설계해 주세요!

채점기는 다음과 같이 플레이어와 통신합니다. 각 줄의 값은 공백으로 구분합니다.

• N은 미로의 크기이며 $11 \le N \le 23$인 정수입니다.
• d는 처음 바라보는 방향이며 U, R, D, L 중 하나입니다.
• a는 발소리 단계이며 $0$ 이상 $3$ 이하의 정수입니다.
• row1부터 rowN까지는 지도의 각 행입니다. 각 줄은 길이가 $N$인 문자열이며, 각 문자는 ?, #, ., P, C, H, X 중 하나입니다. 각 문자의 의미는 문제 설명과 같습니다.
• remaining_ms는 한 판에서 남은 응답 시간이며, 밀리초 단위의 정수입니다.
• 모든 출력 후에는 개행 문자를 출력한 뒤 버퍼를 flush해야 합니다.

예제 프로그램을 실행한 기록의 첫 턴입니다.

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