//Thảo Phạm Nguồn dịch: http://www.usaco.org/index.php?page=viewproblem2&cpid=1134 --------- **MÊ CUNG TAC TOE** Cô bò sữa Bessie rất thích giải các mê cung. Cô ấy cũng thích chơi tic-tac-toe (hay đúng hơn là một phiên bản bò của tic-tac-toe, sẽ được miêu tả bên dưới). Bác nông dân John đã tìm ra một cách mới cho cô ấy để chơi cả hai trò chơi cùng một lúc! Đầu tiên, tic-tac-toe bò: thay vì đặt những chữ *X* và chữ *O* trên một lưới *3 × 3*, những chú bò sẽ chơi với những chữ *M* và chữ O trên một lưới *3 × 3*. Trong mỗi lượt, người chơi đặt chữ *M* hoặc chữ *O* trên một trong các ô trống của lưới (đây là một điểm khác biệt khác với tic-tac-toe cổ điển, nơi một người chơi chỉ luôn đặt chữ *X* và người còn lại chỉ luôn đặt chữ *O)*. Người chiến thắng trò chơi này là người chơi đầu tiên viết *MOO*, theo chiều ngang, chiều dọc hoặc đường chéo. Trò chơi cho phép viết ngược chữ, ví dụ như người chơi có thể thắng bằng cách viết *OOM* trên một trong các đường lưới. Cũng giống như trong tic-tac-toe cổ điển, có khả năng xảy ra bảng với tình trạng không có người chiến thắng. Một bước di chuyển tic-tac-toe bò được xác định bằng 3 ký tự *Mij* hoặc *Oij*, trong đó *i* và *j* là số nguyên trong phạm vi từ 1 đến 3, xác định hàng và cột của ô để đặt ký tự *M* hoặc *O* tương ứng. Để thách thức Bessie, bác nông dân John đã thiết kế một mê cung hình vuông trên một lưới *N × N (3 ≤ N ≤ 25)*. Một số ô, bao gồm tất cả các ô ở biên giới cạnh, chứa các kiện cỏ khô lớn, ngăn không cho Bessie di chuyển đến các ô đó. Bessie có thể di chuyển tự do trên tất cả các ô khác trong mê cung bằng cách thực hiện các bước theo bốn hướng thông thường là bắc, nam, đông, tây. Một số ô chứa một mảnh giấy trên đó có ghi một nước đi tic-tac-toe bò. Trong khi di chuyển qua mê cung, bất cứ khi nào cô ấy đi qua một ô có chứa mảnh giấy, Bessie phải chơi nước đi tương ứng trong trò chơi tic-tac-toe bò mà cô ấy đang chơi đồng thời (trừ trường hợp ô vuông tương ứng trong trò chơi tic-tac-toe đã bị đánh dấu, khi đó cô ấy không cần hành động gì). Cô ấy không có đối thủ trong trò chơi tic-tac-toe phiên bản của bò này, nhưng một số ô trong mê cung có thể là trở ngại của cô ấy với mục tiêu cuối cùng là đánh vần *MOO*. Nếu Bessie ngừng chơi tic-tac-toe bò ngay sau khi cô ấy thắng, hãy xác định xem số cách thiết lập bảng tic-tac-toe chiến thắng khác nhau mà Bessie có thể tạo ra được bằng cách di chuyển một cách thích hợp qua mê cung. **INPUT (nhập dữ liệu vào từ giao diện cửa sổ dòng lệnh Terminal / stdin):** * Dòng đầu tiên chứa số *N*. * *N* dòng tiếp theo, mỗi dòng chứa *3N* kí tự biểu diễn mê cung. Mỗi hình vuông được mô tả bằng một khối gồm 3 ký tự, đó là '###' cho một bức tường, '...' cho một vị trí trống, 'BBB' cho một vị trí không có tường chứa Bessie, và một nước đi tic-tac-toe cho một ô không bị cản, buộc Bessie phải chơi nước đi tương ứng. Một ô sẽ chính xác là BBB. **OUTPUT (in dữ liệu ra giao diện cửa sổ dòng lệnh Terminal / stdout):** * In ra số cách thiết lập bảng tic-tac-toe khác nhau để chiến thắng (có thể bằng 0) mà Bessie có thể tạo ra được khi di chuyển qua mê cung, và dừng lại sau khi cô ấy thắng. **SAMPLE INPUT:** 7 ##################### ###O11###...###M13### ###......O22......### ###...######M22###### ###BBB###M31###M11### ###...O32...M33O31### ##################### **SAMPLE OUTPUT:** 8 Trong ví dụ trên, có 8 cách thiết lập bảng tic-tac-toe chiến thắng khác nhau mà Bessie có thể đạt được sau cùng: 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 trong số những cách trên, hãy xét trường hợp sau: O . . . . . OOM Ở đây, Bessie có thể đến ô O11 trước, sau đó đi dọc xuống và ghé thăm O32, M33 và O31. Và rồi trò chơi kết thúc vì cô ấy đã thắng (do đó cô ấy không thể đến thăm ô M11 ở phía trên vị trí hiện tại của cô tại ô O31). Biên tập và chỉnh sửa bài: Brian Dean