시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 576 | 224 | 187 | 41.372% |
종민이는 CTP에서 만든 AI의 성능을 테스트하기 위해 \(N \times N\) 크기의 격자판에서 오델로 게임을 하고 있다.
오델로 판의 가장 왼쪽 위칸의 좌표는 \((0, 0)\), 가장 오른쪽 아래칸의 좌표는 \((N-1, N-1)\)이다. 오른쪽은 \(x\)좌표가 증가하는 방향, 아래쪽은 \(y\)좌표가 증가하는 방향이다.
오델로는 두 플레이어가 번갈아 가며 한 번씩 돌을 놓는 게임이다. 자신이 돌을 놓은 곳과 판에 이미 놓여있는 자신의 돌 사이에 상대편의 돌만이 적어도 한 개 이상 존재한다면, 사이에 있는 상대편의 돌이 모두 뒤집혀 자신의 돌이 된다. 이와 같이 상대편의 돌을 뒤집을 수 있는 곳에만 돌을 놓을 수 있다.
돌은 가로, 세로, 대각선의 총 8방향으로 뒤집을 수 있으며, 동시에 여러 방향에 있는 돌을 뒤집을 수도 있다. 예를 들어, 아래의 그림에서 X 위치에 흑돌을 놓으면 3개의 백돌이 뒤집혀 흑돌이 된다.
만약 어느 곳에 두어도 상대의 돌을 뒤집을 수 없어서 돌을 놓을 수 없다면, 자신의 차례를 건너뛰고 상대의 차례로 넘어가게 된다.
AI의 성능이 너무 좋은 나머지 종민이는 지금까지 모든 게임을 져버리고 말았다. 알고 있는 모든 수 싸움을 걸어도 이길 수 없었던 종민이는 가장 단순한 방법을 써 보기로 하였다. 그 방법은 자신의 차례에 상대의 돌을 가장 많이 뒤집을 수 있는 곳에 돌을 두는 것이다!
현재 종민이는 흑돌로 플레이하고 있다. 어떤 곳에 두어야 가장 많은 백돌을 뒤집을 수 있을까?
첫째 줄에 오델로 판의 크기 \(N\)이 주어진다.
둘째 줄부터 \(N\)개의 줄에 걸쳐서 오델로 판의 정보를 뜻하는 문자열이 주어진다.
\(i+1\)번째 줄의 \(j\)번째 문자는 오델로 판의 좌표 \((j-1, i-1)\)의 상태를 나타낸다. 각 문자의 의미는 다음과 같다.
.
'은 빈 공간을 나타낸다.W
'는 백돌을 나타낸다.B
'는 흑돌을 나타낸다.빈 공간이 적어도 한 칸 이상 존재함이 보장된다.
첫째 줄에 흑돌을 놓았을 때 가장 많은 백돌을 뒤집을 수 있는 곳을 \((x, y)\) 좌표 순으로 공백으로 구분하여 출력한다.
둘째 줄에 그 좌표에 돌을 두었을 때 뒤집히는 백돌의 개수를 출력한다.
만약 흑돌을 놓을 수 없다면, 대신 첫째 줄에 "PASS
"를 출력한다.
가장 많은 백돌을 뒤집을 수 있는 좌표가 여러 개일 경우엔 \(y\)좌표가 가장 작은 것을, \(y\)좌표도 같다면 그 중 \(x\)좌표가 가장 작은 것을 출력한다.
3 .B. .W. ...
1 2 1
5 .WWWB BWWBB WBWBB WBBWB W...B
0 0 6
8 .WWWWWW. WWWWWWWW WWWWWWWW WWBWWWWW WWWWWWWW WWWWWWWW WWWWWWWW .WWWWWW.
PASS
University > 인하대학교 > 2021 인하대학교 프로그래밍 경진대회(IUPC) B번