Kỳ thi Olympic Lập trình Hoa Kỳ

# Kỳ thi Olympic Lập trình Hoa Kỳ ### USACO 2021 Mỹ mở rộng,Cấp bậc Bạc ### Bài 1: Mê cung tac toe #### Cô bò Bessie rất thích giải mê cung.Cô ấy cũng rất thích chơi tic tac toe,(hoặc nói ngắn gọn hơn là tic tac toe của những chú bò). Bác nông dân John đã tìm ra cách để cô ấy chơi cả 2 trò trong cùng 1 thời điểm!! #### Đầu tiên là tic tac toe của bò: Thay vì đặt những dấu X và O lần lượt trên 1 lưới rộng`3x3`, những chú bò chơi với những dấu M và O trên lưới rộng`3x3`.Ở mỗi lượt chơi của mình , một con bò có thể đặt cả M và O trên một ô trống bất kì(một điểm khác so với tic tac toe bình thường khi một người luôn đánh X và người còn lại phải đánh O).Một bên giành chiến thắng khi bên đó làm xuất hiện chữ 'MOO',kể cả theo hàng dọc,ngang ,chéo hay thậm chí là ngược lại. Chẳng hạn như khi đánh ra được 'OOM' thì vẫn được tính là đã giành chiến thắng.Cũng như tic tac toe thông thường ,có thể hòa nếu không ai trong 2 bên giành chiến thắng.Mỗi nước đi trong trò chơi này được xác định bởi 3 chữ cái riêng biệt như `Mij` và `Oij`,trong đó i và j lần lượt nằm trên khoảng từ `1->3` và có vai trò xác định vị trí của M và O tương ứng. #### Để thử thách Bessie, Bác nông dân John đã thiết kế một mê cung hình vuông bao gồm một lưới `N× N` ô `(3 ≤ N≤ 25)`. Một số ô, bao gồm tất cả các ô ở cạnh, có chứa những đống cỏ khô lớn, ngăn không cho Bessie di chuyển vào bất kỳ ô nào như vậy. Bessie có thể di chuyển tự do giữa tất cả các ô khác trong mê cung, bằng cách thực hiện các nước đi theo 4 hướng thông thường là Bắc, Nam, Đông và Tây. Một số ô chứa một mảnh giấy ,trên đó viết một bước di chuyển bằng tic tac toe. Trong khi Bessie di chuyển quanh trong mê cung, bất kỳ khi nào cô ấy bước vào một ô như vậy, cô ấy phải thực hiện nước đi tương ứng trong khi cô ấy di chuyển qua mê cung (trừ khi ô tương ứng trong trò chơi đã được sử dụng, trong trường hợp đó cô ấy không thực hiện bất kì hành động nào). Cô ấy không có đối thủ trong trò chơi này, nhưng một số ô trong mê cung có thể là đối thủ 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 của bò ngay sau khi chiến thắng,hãy đưa ra số lượng bảng tic tac toe khác nhau để giành chiến thắng mà cô ấy có thể tạo ra bằng cách di chuyển khéo léo qua mê cung. ### **Nội dung nhập vào(nhập bằng stdin)** #### Dòng đầu tiên chứa `N` #### Trong `N` dòng tiếp theo, mỗi dòng chứa `3*N` số nguyên.Mỗi ô được mô tả bằng dãy gồm 3 ký tự,'###' cho các cạnh chắn Bessie, '...' cho một ô trống, 'BBB' cho một cạnh không chắn Bessie và một nước đi đến một ô không có cạnh buộc Bessie phải thực hiện nước đi tương ứng. Chính xác thì một ô sẽ là 'BBB'. ### **Kết quả xuất ra(nhập bằng stdout)** #### Hãy in số lượng bảng tic tac toe khác nhau để giành được chiến thắng(có thể là 0) mà Bessie có thể tạo ra thông qua chuyển động trong mê cung, 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 #### Giải thích: Trong ví dụ này, có 8 bảng chiến thắng khác nhau mà Bessie cuối cùng 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 #### Ta xét 1 trường hợp sau: O.. ... OOM #### Tại đây, Bessie có thể đầu tiên di chuyển đến ô`O[1][1]`, sau đó di chuyển đến các hàng dưới để đi qua `O[3][2]`, `M[3][3]` và `O[3][1]`. Trò chơi sau đó dừng lại, vì cô ấy đã thắng (ví dụ như cô ấy sẽ không thể truy cập ô `M[1][1]` từ chỗ đứng hiện tại của cô ấy `O[3][1]`). #### Biên tập và chỉnh sửa: Brian Dean