Trong trò Join-\(K\), quân đỏ và xanh rơi vào bảng \(N\times N\) dựng đứng, tới ô trống thấp nhất trong cột.

    - Legal Position -

          .......
          .......
          .......
          ....R..
          ...RB..
          ..BRB..
          .RBBR..

   - Illegal Position -

          .......
          .......
          .......
          .......
   Bad -> ..BR...
          ...R...
          .RBBR..

. là ô trống, R đỏ, B xanh. Hình trái hợp lệ; hình phải không hợp lệ vì quân được đánh dấu chưa rơi xuống ô trống bên dưới.

Người chơi thắng nếu có ít nhất \(K\) quân cùng màu liên tiếp theo ngang, dọc hoặc chéo:

      - Four in a row -

     R   RRRR    R   R
     R          R     R
     R         R       R
     R        R         R

Bạn bí mật xoay bảng 90 độ theo chiều kim đồng hồ. Sau khi xoay hoàn toàn, trọng lực làm quân rơi xuống:

    - Start -

     .......
     .......
     .......
     ...R...
     ...RB..
     ..BRB..
     .RBBR..

   - Rotate -

     .......
     R......
     BB.....
     BRRR...
     RBB....
     .......
     .......

   - Gravity -

     .......
     .......
     .......
     R......
     BB.....
     BRR....
     RBBR...

Chỉ được xoay một lần; trọng lực chỉ tác dụng sau khi xoay xong; chỉ xét người thắng sau khi quân rơi xong. Hãy xác định màu nào tạo được \(K\) quân liên tiếp.

Dữ liệu vào

Dòng đầu là \(T\). Mỗi test bắt đầu bằng \(N,K\), rồi \(N\) dòng dài đúng \(N\) mô tả một thế hợp lệ; ban đầu chưa màu nào có \(K\) quân liên tiếp.

Dữ liệu ra

In Case #x: y, với y là Red, Blue, Neither hoặc Both.

Ràng buộc

• \(1\le T\le100\), \(3\le K\le N\); thời gian 30 giây; bộ nhớ 1 GB.

Phân nhóm

• Nhỏ: \(3\le N\le7\).
• Lớn: \(3\le N\le50\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

4
7 3
.......
.......
.......
...R...
...BB..
..BRB..
.RRBR..
6 4
......
......
.R...R
.R..BB
.R.RBR
RB.BBB
4 4
R...
BR..
BR..
BR..
3 3
B..
RB.
RB.

Case #1: Neither
Case #2: Both
Case #3: Red
Case #4: Blue

Nguồn

Google Code Jam 2010, Vòng 1A, bài Rotate.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.