Mê Cung Tic-Tac-Toe

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Bessie di chuyển trong một mê cung $N \times N$ và đồng thời chơi trò tic-tac-toe trên bảng $3 \times 3$ .

Luật tic-tac-toe phiên bản bò: Bảng $3 \times 3$ sử dụng ký tự M và O. Điều kiện thắng: tạo chuỗi MOO theo hàng, cột hoặc đường chéo (bao gồm cả chiều ngược OOM).

Mê cung: Lưới $N \times N$ , mỗi ô biểu diễn bằng 3 ký tự:

###: tường (không đi qua được)
...: ô trống
BBB: vị trí xuất phát của Bessie
Mij hoặc Oij: khi Bessie bước vào ô này, ký tự M hoặc O được đặt vào vị trí $(i, j)$ trên bảng tic-tac-toe (nếu ô đó còn trống)

Bessie di chuyển theo 4 hướng (trên, dưới, trái, phải). Viền mê cung và các ô ### là tường. Trò chơi kết thúc ngay khi bảng tic-tac-toe đạt trạng thái thắng.

Hãy đếm số trạng thái bảng thắng phân biệt mà Bessie có thể đạt được.

Dữ liệu vào

Dòng 1: Số nguyên $N$ ( $3 \leq N \leq 25$ )
$N$ dòng tiếp theo: Mỗi dòng gồm $3 N$ ký tự mô tả mê cung

Dữ liệu ra

Một số nguyên: số trạng thái bảng thắng phân biệt.

Ràng buộc

$3 \leq N \leq 25$

Ví dụ

Input	Output	Giải thích
7 ##################### ###O11###...###M13### ###......O22......### ###...######M22###### ###BBB###M31###M11### ###...O32...M33O31### #####################	8	Bessie có thể đạt được 8 trạng thái bảng thắng khác nhau bằng cách di chuyển theo các đường đi khác nhau trong mê cung.

Bình luận

Không có bình luận tại thời điểm này.