# 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.