# Maze Tac Toe Tác giả: Brian Dean Nguồn đề: USACO 2021 US Open, Silver ## Bài toán Bò Bessie rất thích chơi giải mê cung và tic-tac-toe. Nông dân John đã tìm ra cách để cô có thể chơi cả 2 cùng lúc! Đầu tiên, thay vì tic-tac-toe bản gốc - 2 người chơi luân phiên đặt kí hiệu X/O tương ứng vào 1 ô còn trống trên bảng 3x3 - trong trò cow tic-tac-toe này, mỗi lượt, người chơi sẽ chọn bất kì 1 trong 2 kí hiệu M/O và điền vào 1 trong các ô còn trống. Người đạt được chuỗi MOO, trên hàng ngang, dọc, hoặc đường chéo, đầu tiên là người thắng cuộc. Trường hợp người chơi đạt được chuối đảo (tức là OOM thay vì MOO) thì vẫn được xem là thắng cuộc. Cũng như phiên bản gốc, trong cow tic-tac-toe hoàn toàn có thể xảy ra trường hợp không có người thắng cuộc. 1 nước đi trong cow tic-tac-toe được mô tả dưới dạng `Mij` hoặc `Oij`, trong đó `1 <= i, j <= 3` thể hiện ô cần đặt kí hiệu tương ứng. Để thách đố Bessie, John đã thiết kế một mê cung dạng lưới gồm `N * N` ô (`3 <= N <= 25`). Một số ô (bao gồm tất cả ô nằm trên viền của lưới) chứa những đống rơm lớn ngăn cản Bessie đi vào những ô đó. Bessie có thể đi tự do trong các ô còn lại của lưới bằng cách di chuyển qua các ô kề cạnh với ô đang đứng. Trong các ô có thể đến được, một số ô có chứa mảnh giấy chứa chỉ dẫn dưới dạng `Mij` hay `Oij`. Mỗi khi đến những ô này, Bessie phải thực hiện nước đi đó trong trò chơi cow tic-tac-toe đang được chơi đông thời (nước đi được bỏ qua nếu ô tương ứng không trống). Tuy không có đối thủ trong trò chơi cow tic-tac-toe nhưng một vài chỉ dẫn có thể ngăn cản Bessie đạt được chuỗi `MOO` hay `OOM`. Giả sử Bessie dừng chơi cow tic-tac-toe ngay khi thắng, đếm xem có bao nhiêu cấu hình chiến thắng khác nhau của bảng tic-tac-toe Bessie có thể tạo ra nếu di chuyển trong mê cung hợp lệ. ## Dữ liệu vào Dòng đầu tiên chứa số nguyên `N`. `N` dòng tiếp theo: dòng thứ `i` chứa `3N` kí tự, mỗi ô được biểu diễn bởi 3 kí tự liền kề có 1 trong các dạng sau: - `###` - nếu là ô không thể di chuyển vào - `...` - nếu là ô trống - `BBB` - ô mà Bessie đang đứng ban đầu - `Mij` hay `Oij` - nếu ô đó chứa chỉ dẫn Dữ liệu đảm bảo chỉ có đúng 1 ô duy nhất là `BBB`. ## Dữ liệu ra Số cấu hình chiến thắng khác nhau của bảng tic-tac-toe Bessie có thể tạo ra nếu di chuyển trong mê cung hợp lệ (có thể là 0). ## Bộ dữ liệu mẫu ### Dữ liệu vào mẫu ``` 7 ##################### ###O11###...###M13### ###......O22......### ###...######M22###### ###BBB###M31###M11### ###...O32...M33O31### ##################### ``` ### Dữ liệu ra mẫu ``` 8 ``` ### Giải thích Trong ví dụ trên, có 8 cấu hình chiến thắ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 ``` Lấy ví dụ ở cấu hình đầu tiên ``` O.. ... OOM ``` Khi này, Bessie lần lượt đi đến các ô `(2, 2)`, `(6, 3)`, `(6, 5)`, `(6, 6)`. Trò chơi kết thúc tại đây.