시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 69 | 11 | 10 | 33.333% |
킹과 폰은 체스판에서 진행하는 간단한 게임이다.
흰색은 킹을, 검은색은 폰을 갖고 시작한다. 킹은 판의 아래에서 시작하며 매 차례마다 아래, 위, 대각선 등 8방향으로 한 칸 움직일 수 있다. 검정색은 폰을 갖고 시작하며 매 차례마다 아래로 한칸만 움직일 수 있다. 매 차례마다 양 측은 무조건 자신의 말을 움직여야한다.(두 차례 연속으로 같은 자리에 머물 수 없다)
흰색의 승리 조건은 검은색의 폰을 잡을 경우이고, 검은 폰은 판의 맨 아래 무사히 도착하면 승리한다. 하지만! 게임에는 위 조건 이외에도 승리 조건들이 있다.
이 게임에는 금지 칸과, 위험 칸이 존재하는데, 금지 칸의 경우 양 측 모두 지나서는 안되며, 위험 칸은 오직 검은 폰만 지나갈 수 있다. 일반적인 위험 칸들은 게임 도중에 위치가 바뀌지 않지만, 이 위험 칸들에 더해 최대 2개의 움직이는 위험 칸들이 있다. 이 위험 칸들은 검은 폰의 위치에 따라 좌표가 바뀌는데, 검은 폰에 인접한 왼쪽 아래와 오른쪽 아래에 위치한다. 이 움직이는 위험칸들은 판 밖에 벗어나거나, 금지 칸과 겹치지 않는 이상 유효하다. 위 칸들을 제외한 판 위의 모든 칸들은 열린 칸으로 양 측 모두 드나들 수 있다.
아래의 판을 보자. 금지 칸은 'F', 위험 칸은 'D', 열린 칸은 '.'이고 폰과 킹은 'P'와 'K'이다.
........ ..P....D .D.D..K. .....F.. ..DDD... ..DFDD.. ..DDD... ........
위의 판에서 폰과 킹이 위치한 칸이 열린 칸인지 위험 칸인지는 알수 없으며, 폰 아래의 위험 칸들이 고정되어 있는지, 폰과 함께 움직이는 위험 칸들인지 역시 알 수 없다.
검은 폰의 움직임으로 흰색 킹이 위험 칸에 위치할 수도 있지만, 킹의 경우는 그저 도망쳐버리면 되기에 문제가 되지 않는다.(즉, 폰은 킹을 움직이는 위험 칸으로 잡는 것으로 승리하지 않는다) 하지만, 킹의 폰의 바로 아래 칸에 위치해 길을 막아버릴 경우 폰은 움직일 수 없다.
게임의 승리 조건들은 다음과 같다:
첫째 줄에는 총 테스트케이스의 개수가 주어진다.
이어지는 여덟줄에는 현재 판의 상태가 주어진다. 'F'는 금지 칸, 'D'는 위험 칸, '.'은 열린 칸을 의미한다. 여기서 주어지는 위험 칸의 좌표들은 검은 폰으로써 움직이는 위험 칸들을 제외한 순수 판의 상태이다.
그 다음 두 줄에는 흰색 킹의 좌표(1 ≤ xk, yk ≤ 8)와 검은색 폰의 좌표(1 ≤ xp, yp ≤ 8)가 순서대로 주어진다. 흰색 킹의 최초 좌표는 금지 칸과 고정 된 위험 칸일 수 없으며, 검은 폰의 최초 좌표는 금지 칸일수 없으며, 흰색 킹의 최초 좌표와 다르다.
x는 왼쪽에서부터 세고, y는 아래에서부터 센다.
매 테스트케이스마다 각 줄에 흰색 킹의 승리일 경우 "White"를 검은색 폰의 승리일 경우 "Black"을 출력하라.
2 ........ .......D ........ .....F.. ..DDD... ..DFDD.. ..DDD... ........ 7 6 3 7 ........ ........ ........ ........ ........ ........ ........ ........ 3 1 6 3
Black White
ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2006 Qualification A번