아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

폰 게임

시간 제한1초메모리 제한256 MB

요약
각자 자신의 폰만 앞으로 이동해 모든 열이 막힐 때까지 두는 폰 경주에서 백과 흑 중 승자를 판정합니다.
난이도

어려움10점 중 8점

유형
게임 이론, 동적 계획법
정답자
아직 제출이 없습니다

문제

칼과 네이선은 체스가 너무 쉬워서 재미없다고 생각한다. 그래서 둘은 자기들만의 게임을 만들었다.

게임판은 nn행 mm열이다. 시작할 때 각 열에는 흰 폰 하나와 검은 폰 하나가 놓여 있고, 같은 열에서 흰 폰은 검은 폰보다 아래에 있다. 백은 흰 폰을, 흑은 검은 폰을 움직인다. 백이 먼저 시작해 번갈아 한 수씩 둔다.

한 수는 자기 폰 하나를 앞으로 한 칸 옮기는 것이고, 그 칸은 비어 있어야 한다. 앞은 상대 쪽 방향이라서 흰 폰은 위로, 검은 폰은 아래로 간다. 자기 진영의 첫 줄에 있는 폰, 즉 맨 아랫줄의 흰 폰이나 맨 윗줄의 검은 폰은 앞으로 두 칸을 옮길 수도 있다. 이때는 지나가는 칸과 도착하는 칸이 모두 비어 있어야 한다. 일반 체스와 달리 폰은 잡히지 않고, 열을 바꾸지도 않는다.

맨 아랫줄에 있는 흰 폰의 위 두 칸이 비어 있으면 그 폰으로 둘 수 있는 수는 한 칸 전진과 두 칸 전진, 두 가지다. 바로 앞 칸이 막힌 폰으로는 아무 수도 둘 수 없다.

수를 계속 두면 모든 열에서 두 폰이 맞닿아 양쪽 다 둘 수 있는 수가 없어진다. 그 시점에 게임이 끝나고, 마지막으로 수를 둔 사람이 이긴다.

두 사람이 모두 최선으로 둘 때 누가 이기는지 구하라.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 이 값은 100 이하의 자연수다. 각 테스트 케이스는 다음과 같이 주어진다.

  • 첫 줄에 판의 행 수 nn과 열 수 mm이 주어진다. (3≤n≤203 \le n \le 20, 1≤m≤201 \le m \le 20)
  • 다음 nn개 줄에 각각 mm개의 문자로 시작 위치가 주어진다. 위쪽 줄부터 아래쪽 줄 순서다. W는 흰 폰, B는 검은 폰, .은 빈 칸이다. 각 열에는 W와 B가 정확히 하나씩 있고, W가 B보다 아래에 있다.

모든 테스트 케이스에서 백이 둘 수 있는 수가 적어도 하나 있다.

출력

각 테스트 케이스마다 한 줄씩 출력한다. 백이 최선으로 두어 이길 수 있으면 White wins를, 흑에게 이기는 전략이 있으면 Black wins를 출력한다.

예제3

  1. 예제 1

    입력
    5
    8 8
    .....BB.
    B.......
    W......B
    ...B.W..
    ..B.....
    .B......
    ...WB..W
    .WW.W.W.
    6 4
    ....
    B..B
    ....
    .B.W
    W.B.
    .WW.
    5 3
    ...
    BBB
    ...
    WW.
    ..W
    4 6
    .BBB.B
    B...B.
    ...W..
    WWW.WW
    7 7
    .B.B..B
    .......
    ..B.B..
    B....B.
    .......
    ...WW.W
    WWW..W.
    
    예상 출력
    Black wins
    Black wins
    White wins
    White wins
    Black wins
    
  2. 예제 2

    입력
    1
    3 1
    B
    .
    W
    
    예상 출력
    White wins
    
  3. 예제 3

    입력
    3
    5 1
    .
    B
    .
    .
    W
    5 1
    B
    .
    .
    W
    .
    6 1
    .
    B
    .
    .
    W
    .
    
    예상 출력
    White wins
    Black wins
    Black wins