USACO 2021, Bảng Bạc

# USACO 2021, Bảng Bạc ## Bài 1. Ma trận caro Cô bò Bessie rất thích giải các mê cung và cũng vô cùng thích chơi cờ caro (phiên bản dành cho bò). Anh nông dân John đã tìm ra cách giúp cho cô bò của chúng ta có thể thể hiện khả năng của mình ở 2 trò chơi cùng một lúc. Đầu tiên là cờ caro kiểu con bò: Thay vì chơi **X** và **O** trên bảng $3 \times 3$ truyền thống thì người chơi sẽ chơi **M** và **O** trên bảng $3 \times 3$. Tại mỗi lượt, người chơi hiện tại có thể đặt hoặc là ký tự **'M'** hoặc là ký tự **'O'** tại bất kỳ ô trống nào (đây là 1 điểm khác biệt so với cờ caro truyền thống, nơi mà 1 người chơi chỉ được chơi **X** và người còn lại chỉ được chơi **O**). Người chiến thắng là người đầu tiên làm xuất hiện được xâu **"MOO"** hoặc **"OOM"** trên cùng 1 hàng, cùng 1 cột hay cùng 1 đường chéo. Một nước đi được ký hiệu bởi 3 ký tự, hoặc là **"Mij"** hoặc là **"Oij"**, ở đó $i$ là vị trí cột, $j$ là vị trí hàng của nước đi với ký tự **'M'**, **'O'** tương ứng. Để thách đấu Bessie, nông dân John đã thiết kế một mê cung hình vuông gồm $N \times N$ ô $\left(3 \leq N \leq 25\right)$. Một số ô, bao gồm các ô ở biên, có chứa các đống cỏ khô lớn (có thể gọi đây là tường), ngăn Bessie tiến đến các ô như vậy. Bessie có thể di chuyển tự do đến các ô khác của mê cung theo 4 hướng đông, tây, nam, bắc. Một số ô có chứa một mảnh giấy ghi nước đi của cờ caro bò, bất cứ khi nào Bessie di chuyển đến một ô như vậy, cô bò bắt buộc phải thực hiện nước đi tương ứng trong trò caro đó (trừ khi ô trong cờ caro bò đã bị chiếm, khi đó Bessie không phải làm gì). Trong trò chơi này, Bessie không phải đấu với bất kỳ ai cả, tuy nhiên một vài ô trong mê cung có thể ngăn cản cô tiến đến mục tiêu làm xuất hiện được xâu **"MOO"** hoặc **"OOM"**. Giả sử Bessie dừng chơi ngay lập tức sau khi thắng cờ caro bò, hãy xác định số lượng các cấu hình chiến thắng trong cờ caro bò mà Bessie có thể sinh ra bằng cách di chuyển trong mê cung. ### Input Dòng đầu tiên chứa một số nguyên $N$. Mê cung được miêu tả trong $N$ dòng tiếp theo, mỗi dòng chứa $3N$ ký tự. Mỗi ô trong mê cung được biểu diễn bởi 3 ký tự: hoặc là **"\#\#\#"** (tường), hoặc là **"..."** (ô trống), hoặc là **"BBB"** (ô không phải tường mà Bessie đang đứng), hoặc là một nước đi của cờ caro bò trên một ô trống của ma trận. Dữ liệu đảm bảo chỉ có một ô **"BBB"**. ### Output In ra số lượng các cấu hình chiến thắng trong cờ caro bò mà Bessie có thể sinh ra bằng cách di chuyển trong mê cung. ### Ví dụ #### Input ``` 7 ##################### ###O11###...###M13### ###......O22......### ###...######M22###### ###BBB###M31###M11### ###...O32...M33O31### ##################### ``` #### Output ``` 8 ``` ### Giải thích Có tổng cộng 8 cấu hình mà Bessie có thể tạo ra: ``` O.M .O. MOM O.. .O. .OM O.M .O. .OM O.. .O. MOM O.. ... OOM ..M .O. OOM ... .O. OOM ... ... OOM ``` Cụ thể hơn, xét trường hợp sau ``` O.. ... OOM ``` Tại đây, Bessie di chuyển như sau: **"O11"** --> **"O32"** --> **"M33"** --> **"O31"**