Bessie thích giải mê cung. Cô cũng thích chơi cờ ca-rô ba ô, hay chính xác hơn là phiên bản dành cho bò được mô tả dưới đây. Farmer John đã tìm ra một cách mới để cô chơi cả hai trò cùng lúc!

Trước hết là cờ ca-rô dành cho bò. Thay vì đặt X và O trên bảng \(3\times3\), những chú bò dùng M và O trên bảng \(3\times3\). Trong mỗi lượt, người chơi có thể đặt M hoặc O vào một ô trống bất kỳ. Đây cũng là một điểm khác với cờ ca-rô thông thường, nơi một người luôn đánh X và người kia luôn đánh O. Người chiến thắng là người đầu tiên ghép được MOO theo chiều ngang, dọc hoặc chéo. Đọc ngược cũng được tính, ví dụ có thể thắng bằng cách ghép OOM trên một hàng. Giống cờ ca-rô thông thường, có thể xuất hiện trạng thái bảng không có người thắng. Một nước đi thường được biểu diễn bằng ba ký tự, có dạng Mij hoặc Oij, trong đó \(i\) và \(j\) đều thuộc phạm vi \(1\ldots3\), lần lượt chỉ hàng và cột để đặt chữ cái tương ứng.

Để thử thách Bessie, Farmer John thiết kế một mê cung hình vuông gồm lưới \(N\times N\) ô (\(3\le N\le25\)). Một số ô, bao gồm toàn bộ các ô biên, chứa những kiện cỏ khô lớn nên Bessie không thể bước vào. Bessie có thể di chuyển tự do giữa các ô còn lại bằng cách bước theo bốn hướng bắc, nam, đông và tây.

Một số ô chứa mảnh giấy ghi một nước đi. Trong khi di chuyển qua mê cung, mỗi khi bước lên một ô như vậy, Bessie bắt buộc thực hiện nước đi tương ứng trong ván cờ mà cô đang chơi đồng thời, trừ khi ô tương ứng trên bảng cờ đã có chữ cái; trong trường hợp đó cô không làm gì. Bessie không có đối thủ trong ván cờ này, nhưng một số ô trong mê cung có thể cản trở mục tiêu cuối cùng ghép được MOO của cô.

Giả sử Bessie ngừng chơi ngay khi chiến thắng. Hãy xác định số cấu hình bảng cờ chiến thắng phân biệt mà cô có thể tạo ra bằng cách di chuyển thích hợp qua mê cung.

Dữ liệu vào

Dòng đầu tiên chứa \(N\).

Mỗi dòng trong \(N\) dòng tiếp theo chứa \(3N\) ký tự mô tả mê cung. Mỗi ô được mô tả bằng một khối ba ký tự:

• ### là tường;
• ... là ô trống;
• BBB là ô không phải tường và chứa Bessie;
• một nước đi cờ bò là ô không phải tường, buộc Bessie thực hiện nước đi tương ứng.

Có đúng một ô BBB.

Dữ liệu ra

In số cấu hình bảng cờ bò chiến thắng phân biệt, có thể bằng \(0\), mà Bessie có thể tạo ra bằng cách di chuyển trong mê cung và dừng lại sau khi chiến thắng.

Phân nhóm

Tất cả các test tuân theo các ràng buộc đã nêu.

Ví dụ

7
#####################
###O11###...###M13###
###......O22......###
###...######M22######
###BBB###M31###M11###
###...O32...M33O31###
#####################

8

Trong ví dụ này, Bessie có thể đạt được tám cấu hình bảng chiến thắng sau:

O.M
.O.
MOM

O..
.O.
.OM

O.M
.O.
.OM

O..
.O.
MOM

O..
...
OOM

..M
.O.
OOM

...
.O.
OOM

...
...
OOM

Để giải thích một trong các cấu hình trên, xét trường hợp:

O..
...
OOM

Bessie có thể đến ô O11 trước, sau đó di chuyển đến hành lang phía dưới và lần lượt đi qua O32, M33, O31. Ván cờ kết thúc tại đó vì cô đã thắng; chẳng hạn, cô không thể tiếp tục đến ô M11 nằm phía bắc vị trí hiện tại trên ô O31.

Nguồn

USACO 2021 US Open, Silver - Maze Tac Toe: https://usaco.org/index.php?page=viewproblem2&cpid=1134

Tác giả: Brian Dean.