Bò trong tiệm đồ sứ

Điểm: 1,00 (OI)

Giới hạn thời gian: 4.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 đã vô tình làm vỡ một bức tượng nhỏ quý giá trong tiệm đồ sứ. Bức tượng bị vỡ thành nhiều mảnh. Farmer John muốn tìm xem có bao nhiêu bộ đúng 3 mảnh có thể ghép lại thành bức tượng ban đầu.

Bức tượng ban đầu và các mảnh vỡ đều được biểu diễn trên lưới ô vuông. Mỗi ô có thể rỗng (.) hoặc được tô màu bằng một chữ cái thường. Khi ghép 3 mảnh để tạo thành bức tượng:

Mỗi mảnh có thể được dịch chuyển (tịnh tiến), xoay (90°, 180°, 270°) và/hoặc lật (theo trục ngang) trên lưới.
Các mảnh không được chồng lên nhau (mỗi ô được tô màu của bức tượng phải được phủ bởi đúng 1 mảnh).
Hợp của 3 mảnh sau khi biến đổi phải khớp chính xác với bức tượng ban đầu, bao gồm cả màu sắc.

Một bộ là tập hợp 3 mảnh không quan tâm đến thứ tự. Nếu có các mảnh giống hệt nhau, mỗi mảnh được coi là một thực thể riêng biệt.

Dữ liệu vào

Dòng đầu: số nguyên $K$ — số lượng mảnh vỡ (không kể bức tượng ban đầu).
Dòng tiếp theo là mô tả bức tượng ban đầu (mục tiêu):
- Dòng đầu: hai số nguyên $R$ và $C$ — kích thước lưới.
- $R$ dòng tiếp theo, mỗi dòng có $C$ ký tự là . hoặc chữ cái thường.
Tiếp theo là $K$ khối mô tả các mảnh vỡ (cùng định dạng).

Dữ liệu ra

In ra một số nguyên duy nhất — số bộ đúng 3 mảnh (chọn từ $K$ mảnh vỡ) có thể ghép thành bức tượng ban đầu.

Ràng buộc

$4 \leq K \leq 100$
Mỗi mảnh có kích thước tối đa $500 \times 500$
Lưới của bức tượng ban đầu có kích thước tối đa $500 \times 500$

Ví dụ

Input	Output	Giải thích
5 5 5 aaaaa ..a.. bbabb ..a.. aaaaa 3 5 ..abb ..a.. aaaaa 5 2 a. a. aa a. a. 1 2 bb 1 5 bbabb 2 5 aaaaa ..a..	3	Bức tượng mục tiêu là hình chữ thập 5×5 với màu `a` và `b`. Có 5 mảnh vỡ. Có 3 bộ 3 mảnh hợp lệ có thể ghép thành bức tượng (kể cả xoay và lật).

Ghi chú

Mỗi mảnh có thể được dịch chuyển (tịnh tiến), xoay, và lật.
Hai mảnh có hình dạng và màu sắc giống nhau được coi là phân biệt nếu chúng là hai mảnh khác nhau trong danh sách đầu vào.
Kết quả có thể rất lớn (lên tới hàng trăm nghìn).

Bình luận

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