# **USACO 2021 US Open, Silver** ## **Problem 1. Maze Tac Toe** Bò Bessie thích chơi giải mã mê cung. Cô cũng thích chơi cờ caro (hay đúng hơn là phiên bản bò của cờ caro). Bác nông dân John đã tìm ra một cách mới để cô ấy có thể chơi hai trò chơi cùng một lúc! Đầu tiên, cờ caro bò cũng chơi trên bảng $3 \times 3$, nhưng thay vì đánh 'X' và 'O', thì chúng ta lại dùng 'M' và 'O'. Trong mỗi lượt, mỗi người chơi có thể đặt 'M' hoặc 'O' vào bất cứ ô nào còn trống trên bảng (đây là một khác biệt so với cờ caro tiêu chuẩn khi mà khi một người chơi đã dùng 'X' thì người còn lại phải dùng 'O'). Người chiến thắng của trò chơi là người đầu tiên mà tạo được từ 'MOO', bất kể là theo đường ngang dọc hay là chéo. Kể cả việc đánh vần người lại cũng được chấp nhận, ví dụ một người có thể thắng nếu đánh vần được 'OOM' trên một hàng của bảng. Giống như trò chơi cờ caro tiêu chuẩn thì trong trò chơi này, bảng trò chơi hoàn toàn có thể rơi vào trạng thái hòa mà không có ai có thể thắng. Một lượt chơi trong trò chơi này thường được ghi theo định dang 'Mij' hoặc 'Oij' với $i$ và $j$ năm trong khoảng từ $1...3$ xác định hàng và cột của vị trí đánh 'M' hay 'O'. Để thử thách Bessie, bác nông dân John đã thiết kế một mê cung hình vuông dạng $N \times N$ ô ($3 \leqslant N \leqslant 25$). Một vài ô trong mê cung này, kể cả các ô ở biên, có thể có những đống cỏ khô, làm cho Bessie không thể di chuyển được vào những ô này. Bessie có thể di chuyển tự do tất cả các ô còn lại trong mê cung theo 4 hướng bắc, nam, đông, tây. Một vài ô trong mê cung có một mảnh giấy mà trên đó ghi một nước đi trên trò chơi cờ caro bò. Mỗi khi bò Bessie đi đến một ô như thế thì cô buộc phải đánh nước đi tương ứng trên trò chơi cờ caro bò mà cô đang chơi (nếu ô tương ứng trên bảng trò chơi đã được đánh thì cô sẽ không thực hiện nước đi này). Trong trò chơi cờ caro lần này, cô không có đối thủ, tuy nhiên một vài ô trong mê cung có thể sẽ cản trở mục tiêu đánh vần được từ 'MOO' của cô. Nếu Bessie ngay lập tức ngừng chơi cờ caro bò khi cô thắng, hãy xác định số trạng thái bảng mà cô có thể thắng bằng cách di chuyển lần lượt trong mê cung. ### Input Dòng đầu tiên bao gồm số $N$. Mê cung được mô tả trong $N$ dòng sau, mỗi dòng gồm $3N$ chữ cái. Mỗi ô được mô tả bằng một khối 3 chữ cái liên tiếp, trong đó '###' dùng để miêu tả một bức tường, '...' là một ô trống, 'BBB' là một ô trống chứa Bessie, và các ô còn lại là các nước đi trên trò chời cờ caro bò. Chỉ có duy nhất một ô là 'BBB'. ### Output In ra số trạng thái bảng cờ caro bò (có thể là 0) mà Bessie có thể thắng bằng cách di chuyển trong mê cung và dừng lại ngay lập tức khi thắng. ### Sample Input ``` 7 ##################### ###O11###...###M13### ###......O22......### ###...######M22###### ###BBB###M31###M11### ###...O32...M33O31### ##################### ``` ### Sample Output ``` 8 ``` Trong ví dụ này, có 8 trạng thái bảng 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 ví dụ này, ta có thể lấy 1 trường hợp: ``` O.. ... OOM ``` Ở đây, Bessie có thể đã đi vào ô O11 và xuống những hàng dưới và đi vào O32, M33 và O31.