# USACO 2021 US OPEN, Silver ## Vấn đề 1. MAZE TAC TOE --- Cô bò Bessie thích rất thích giải mê cung. Song, cô cũng thích chơi $Tic-Tac-Toe$ (phiên bản dành cho những cô bò). Anh nông dân John đã nảy ra ý tưởng giúp cô có thể chơi cùng lúc cả 2 trò. Đầu tiên, ở trò $Tic-Tac-Toe$ dành cho bò, thay vì điền $X$ hoặc $O$ vào bảng ô vuông $3\times3$, cô bò sẽ điền kí tự $M$ hoặc $O$. Ở mỗi lượt chơi, cô có thể đặt hoặc là $M$ hoặc là $O$ tại một ô trống (khác với phiên bản thông thường là một người chỉ được điền $X$ và người còn lại điền $O$). Người chiến thắng của trò chơi này chính là người đầu tiên có thể điền được từ $MOO$ bất kể hàng ngang, hàng dọc, hay đường chéo. Và chiều ngược lại cũng được tính, ví dụ người chơi có thể có $OOM$ trên một hàng. Tuy nhiên như bản gốc, trường hợp người chơi không thể thắng cũng có thể xảy ra. Mỗi lượt chơi được kí hiệu bởi 3 kí tự $Mij$ hoặc $Oij$, với $i,j \in [1,3]$ ($i$ là số dòng, $j$ là số cột), thể hiện cho vị trí trong bảng mà ta điền vào kí tự $M$ hoặc $O$ tương ứng. Để thử thách Bessie, anh nông dân John đã thiết kế một mê cung hình vuông có kích thước $N \times N$, $(3 \leq N \leq 25)$ được tạo từ các ô vuông đơn vị. Một số ô, bao gồm tất cả các ô ở cạnh bảng, sẽ có chướng ngại vật ngăn không cho Bessie đi tới. Bessie có thể di chuyển tự do ở các ô không có chướng ngại vật theo 4 hướng **ĐÔNG, TÂY, NAM, BẮC**. Một số ô sẽ có 1 mảnh giấy chứa thông tin của một lượt chơi của trò $Tic-Tac-Toe$ dành cho Bessie. Trong khi giải mê cung, mỗi khi Bessie bước đến các ô có mảnh giấy chứa thông tin về lượt chơi, cô buộc phải thực hiện lượt chơi ấy (trường hợp cô đã đến ô này trước đó thì cô không làm gì). Cô không có đối thủ cùng tham gia trò chơi. Tuy nhiên một số ô trong mê cung sẽ ngăn cô ấy hoàn thành từ $MOO$. Giả sử Bessie dừng trò chơi ngay khi thắng, hãy xác định số cấu hình chiến thắng phân biệt trong trò chơi $Tic-Tac-Toe$ mà cô ấy có thể đạt được trong quá trình giải mê cung. ## INPUT (nhập từ bàn phím / stdin) Dòng đầu tiên là $N$. $N$ dòng tiếp theo chứa $3 \times N$ kí tự. >Mỗi ô trong mê cung được mô tả bởi một khối gồm 3 kí tự, **'###'** là chứa ngại vật, **'...'** là không gian trống, **'BBB'** là vị trí của Bessie. Khi di chuyển Bessie đến ô có thông tin lượt chơi, cô bắt buộc phải thực hiện lượt chơi đó. Vị trí của Bessie là duy nhất. ## OUTPUT (màn hình / stdout) In ra số lượng cấu hình thỏa yêu cầu đề bài. > Số cấu hình có thể là 0. ## VÍ DỤ ### Input: ``` 7 ##################### ###O11###...###M13### ###......O22......### ###...######M22###### ###BBB###M31###M11### ###...O32...M33O31### ##################### ``` ### Output: ```8``` Ở ví dụ trên, 8 là số cấu hình chiến thắng tối đa mà Bessie có thể đạt được. ``` 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 các kết quả trên, xét trường hợp sau: ``` O.. ... OOM ``` Ở đây Bessi có thể thăm ô $O11$ đầu tiên rồi di chuyển đến các ô $O32$ rồi $M33$ rồi $O31$. Trò chơi dừng lại sau đó khi Bessie đã thắng (chính vì vậy mà Bessie sẽ không thể đi đến ô $M11$).