Bố trí tám cảm biến không xung đột

Bối cảnh và bài toán

Một sàn 8×8 cần đặt đúng 8 cảm biến. Mỗi hàng, cột và hai đường chéo chỉ được có tối đa một cảm biến; một số ô bị khóa và không được đặt. Cần đếm số cấu hình hợp lệ.

Yêu cầu

Đếm số cách đặt đủ 8 cảm biến thỏa mọi điều kiện.

Input

• 8 dòng, mỗi dòng 8 ký tự: . là ô dùng được, * là ô bị khóa.

Output

In số cấu hình hợp lệ.

Ràng buộc

• Bảng luôn có kích thước 8 x 8

Chấm điểm

Ví dụ 1

Input

........
........
........
........
........
........
........
........

Output

92

Giải thích. Bàn cờ trống có 92 cách đặt tám quân hậu/cảm biến không tấn công nhau.

Ví dụ 2

Input

********
........
........
........
........
........
........
........

Output

0

Giải thích. Hàng đầu tiên không có vị trí hợp lệ nên không thể đặt đủ 8 cảm biến.

Thông tin bài tập

Nguồn: Phỏng theo CSES Problem Set — Chessboard and Queens (Task 1624).

Tham khảo: https://cses.fi/problemset/task/1624