판 회전
시간 제한5초메모리 제한512 MB
보드판을 시계 방향으로 90도 돌려 말을 가라앉힌 뒤 빨강과 파랑 중 K개를 이은 쪽을 판정합니다.
문제
Join-K 게임에서 두 사람은 N × N 판에 빨간 말과 파란 말을 떨어뜨린다. 판은 세워져 있어서, 떨어뜨린 말은 그 열에서 가장 아래에 있는 빈 칸까지 내려간다.
다음 배치는 올바르다.
.......
.......
.......
....R..
...RB..
..BRB..
.RBBR..
다음 배치는 올바르지 않다.
.......
.......
.......
.......
..BR...
...R...
.RBBR..
'.'은 빈 칸, 'R'은 빨간 말, 'B'는 파란 말이다. 두 번째 판이 올바르지 않은 까닭은 셋째 열의 파란 말이 아래의 빈 칸으로 내려가지 않고 그 위에 남아 있기 때문이다.
한 색의 말 K개가 가로, 세로, 또는 두 대각선 중 하나를 따라 연속으로 놓이면 그 색의 플레이어가 이긴다. K가 4일 때 네 방향은 다음과 같다.
R RRRR R... ...R
R .R.. ..R.
R ..R. .R..
R ...R R...
위의 올바른 판에서는 두 플레이어 모두 같은 색 말을 두 개까지만 연속으로 놓았고, 세 개를 연속으로 놓은 쪽은 없다.
지금 Join-K 게임을 하고 있고, 계획이 하나 있다. 상대가 다른 곳을 보는 사이에 판 전체를 시계 방향으로 90도 돌린다. 그러면 중력이 새로운 방향으로 모든 말을 아래로 끌어내린다.
처음 상태:
.......
.......
.......
...R...
...RB..
..BRB..
.RBBR..
시계 방향으로 90도 돌린 뒤:
.......
R......
BB.....
BRRR...
RBB....
.......
.......
중력이 작용한 뒤:
.......
.......
.......
R......
BB.....
BRR....
RBBR...
상대가 알아채기 전에 돌릴 시간은 한 번뿐이다. 처음 판이 주어지면, 회전과 중력이 모두 끝난 뒤 어느 플레이어가 같은 색 말 K개를 연속으로 놓게 되는지 구하라.
규칙:
- 판은 한 번만 회전할 수 있다.
- 중력은 회전이 완전히 끝난 뒤에만 작용한다.
- 승자는 중력이 끝난 뒤에만 확인한다.
입력
첫 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫 줄에는 N과 K가 주어진다. 이어지는 N개의 줄에는 각각 정확히 N개의 문자가 주어지며, 위와 같은 형식으로 처음 판을 나타낸다.
처음 판은 항상 Join-K 게임에서 나올 수 있는 올바른 배치다. 특히 어느 플레이어도 아직 K개를 연속으로 놓지 않았다.
제한:
출력
각 테스트 케이스마다 "Case #x: y" 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 Red, Blue, Neither, Both 중 하나다. 빨간 플레이어만 K개를 연속으로 놓게 되면 Red, 파란 플레이어만 그러면 Blue, 둘 다 그러면 Both, 아무도 그러지 못하면 Neither를 출력한다.