# USACO 2021 US Open, Silver
## Problem 1: Maze Tic-tac-toe
Cô bò Bessie rất yêu thích trò chơi giải mã mê cung và trò chơi đánh cờ ca-rô phiên bản dành riêng cho loài bò (sẽ được mô tả ngay sau đây). Anh nông dân John đã tìm ra một phương pháp mới giúp cô bò Bessie có thể chơi cả 2 trò chơi nêu trên cùng một lúc!

Đầu tiên, trò chơi ca-rô dành cho loài bò không giống như những ván ca-rô khác: Thay vì đánh “X” và “O” vào một bàn cờ 3x3, những con bò sẽ phải đánh kí tự “M” và “O” vào bàn cờ 3x3. Khi đến lượt, những con bò có quyền được đánh kí tự “M” hoặc kí tự “O” bất kì, thay vì một người chơi chỉ được đánh cố định một kí tự “M” hoặc “O”. Con bò chiến thắng trò chơi này sẽ là con bò đầu tiên hoàn thành dãy kí tự “M-O-O”, liền nhau theo chiều dọc, chiều ngang hoặc theo đường chéo. Con bò cũng có thể thắng nếu là người thi đấu đầu tiên hoàn thành dãy kí tự trên theo chiều ngược lại: “O-O-M”, liền nhau theo chiều dọc, chiều ngang hoặc theo đường chéo. Tương tự như những ván cờ ca-rô thông thường, ca-rô dành riêng cho loài bò cũng có thể không có người chiến thắng khi ván cờ lâm vào một vài trường hợp nhất định. Mỗi lượt đánh của người tham gia được xác định bởi 3 kí tự, ví dụ: “Mij” hoặc “Oij”, với i và j lần lượt là số hàng số cột (từ 1 đến 3) để đánh kí tự “M” hoặc “O”.

Để gia tăng phần hấp dẫn, John đã thiết kế một mê cung hình vuông với NxN ô (3≤N≤25). Trong mê cung, Bessie không thể di chuyển tới một số ô nhất định bao gồm những ô tường và những ô có vật cản lớn. Còn đối với những ô khác trong mê cung, Bessie có thể di chuyển tự do theo 4 hướng: Đông, Tây, Nam, Bắc. Trong mê cung sẽ có một vài ô nhất định được đặt những mảnh giấy ghi thông tin nước đi cần đánh trong ca-rô bò. Bất kì khi nào Bessie bước vào một ô đã đặt sẵn mảnh giấy như vậy, Bessie sẽ phải đánh “M” hoặc “O” theo chỉ dẫn của mảnh giấy (ngoại trừ trường hợp ô đó đã được đánh trước đó, khi đó Bessie sẽ không thao tác). Bessie không có đối thủ khi chơi ca-rô bò, nhưng một vài ô ở trong mê cung sẽ ngăn cản việc hoàn thành dãy kí tự “M-O-O” để đi tới chiến thắng.

Bessie sẽ dừng chơi ca-rô bò ngay sau khi chiến thắng, hãy xác định số trường hợp khác nhau mà Bessie có thể chiến thắng trò chơi caro-bò bằng việc di chuyển một cách hợp lý qua mê cung.

**INPUT FORMAT (terminal/ stdin):**
Dòng đầu tiên của input là N

Mê cung sẽ được xác định bởi N dòng tiếp theo, mỗi dòng có 3N kí tự. Mỗi ô được xác định bởi 1 block bao gồm 3 kí tự với format: ‘###’ là tường, ‘BBB’ là ô đánh dấu Bessie đang ở đó (không phải tường), và những nước đi định sẵn đặt ở trên một số ô còn lại. Sẽ chỉ có duy nhất 1 ô ‘BBB’

**OUTPUT FORMAT (terminal/ stdout):**

Hãy in ra số trường hợp mà Bessie có thể thắng trò chơi ca-rô bò bằng cách di chuyển hợp lý qua mê cung và dừng lại khi Bessie thắng cuộc.

**SAMPLE INPUT:**
7

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

**SAMPLE OUTPUT:**
8
Ở ví dụ này, có 8 trường hợp riêng biệt để Bessie có thể dành chiến thắng:

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, hãy xem trường hợp sau:

O..
...
OOM

Tại đây, trước tiên Bessie di chuyển tới ô O11, sau đó di chuyển dọc xuống dưới và đi qua O32, M33 và O31. Trò chơi sau đó dừng lại, vì Bessie đã dành được chiến thắng (ví dụ như cô ấy sẽ không thể di chuyển tới ô M11 ở phía bắc so với vị trí hiện tại của mình trên ô O31).

Problem credits: Brian Dean