---
# System prepended metadata

title: 'USACO 2021 US Open, Silver - Bài 1. Mê Cung Caro'

---

# USACO 2021 US Open, Silver - Bài 1. Mê Cung Caro


Bò Bessie rất thích giải các mê cung. Nó cũng rất thích chơi ca-rô (bản dành cho bò, sẽ được nói ở dưới). Ông John nông dân đã nghĩ ra một cách để nó có thể chơi hai trò cùng một lúc!

* Trò ca-rô dành cho bò: Thay vì đặt $X$ và $O$ trên các ô 3x3, ta sẽ đặt $M$ và $O$ trên các ô 3x3 đó. Trong mỗi lượt ta có thể đặt $M$ hoặc $O$ trên bất kì ô trống nào (khác so với một trò ca-rô bình thường: một người chỉ có thể đặt $X$ hoặc $O$ cho tới cuối ván). Người thắng cuộc sẽ là người đầu tiên tạo được chuỗi $MOO$ theo chiều ngang, chiều dọc, hoặc đường chéo, hoặc có thể vần ngược lại.
* Ví dụ, ta thắng nếu như ta tạo được một chuỗi $OOM$ hoặc $MOO$ trên bảng đó, vẫn có trường hợp không ai thắng như trong một ván ca-rô bình thường. Một nước đi trong trò này được chỉ định bởi 3 ký tự: $M_{i, j}$ hoặc là $O_{i, j}$ trong đó $i$ và $j$ đều thuộc đoạn $1...3$, được chỉ định hàng và cột tương ứng để đặt $M$ và $O$.

Để tăng độ khó, John đã thiết kế một mê cung hình vuông bao gồm một lưới $N \times N$ ô $(3 \leq N \leq 25)$. Tất cả các ô ở viền ngoài có chứa những bức tường để ngăn không cho Bessie đi vào các ô đó, ngoài ra các ô còn lại có thể đi vào được theo $4$ hướng thông thường là Đông, Tây, Nam, Bắc. Một số ô chứa các thông tin ghi nước đi của trò ca-rô. Khi di chuyển xung quanh mê cung mà đi vào một ô như thế, Bessie phải thực hiện một hành động tương ứng trong trò ca-rô mà cô ấy đang chơi cùng lúc *(trừ khi ô ca-rô đó đã được sử dụng, Bessie không cần phải làm gì)*. Cô ấy không có đối thủ, nhưng một số ô trong mê cung có thể đánh bại Bessie bằng cách ghi được $MOO$.

Nếu Bessie ngừng chơi ngay sau khi chiến thắng, hãy xác định số cấu hình bảng ca-rô mà cô ấy có thể hoàn thành khi di chuyển qua mê cung?

## **Quy ước đầu vào**
* Dòng đầu tiên chứa số $N$ $(3 \leq N \leq 25)$
* Mê cung được xác định bởi $N$ dòng tiếp theo, mỗi dòng chứa $3N$ kí tự, được mô tả bằng ***###*** cho bức tường, ***...*** cho không gian trống, ***BBB*** bao gồm Bessie, và một hướng di chuyển theo ca-rô ($M_{i, j}$) mà cô ấy phải thực hiện theo. Chính xác một ô sẽ là ***BBB***

## **Quy ước đầu ra**

In số cấu hình bảng ca-rô khác nhau mà Bessie đã chiến thắng

## **Ví dụ đầu vào**
```
7
#####################
###O11###...###M13###
###......O22......###
###...######M22######
###BBB###M31###M11###
###...O32...M33O31###
#####################
```

## **Ví dụ đầu ra**

8
Trong ví dụ này, có 8 cấu hình mà Bessie có thể đạt được: 
```
O.M    O..    O.M    O..    O..    ..M    ...    ...
.O.    .O.    .O.    .O.    ...    .O.    .O.    ...
MOM    .OM    .OM    MOM    OOM    OOM    OOM    OOM
```
Hãy giải thích một trong những cái này, ví dụ:
```
O..
...
OOM
```
Bessie có thể đến ô $O_{1, 1}$ trước tiên, sau đó di chuyển xuống dưới đến $O_{3, 2}$, $M_{3, 3}$ và $O_{3, 1}$. Đến đây là dừng vì Bessie đã thắng (ví dụ cô ấy không thể đến ô $M_{1, 1}$ ở phía bắc khi ở vị trí hiện tại của mình trên $O_{3, 1}$).

### Nguồn bài tập: Brian Dean.