Duyệt tranh khảm
Đề bài
Mô tả
Trung tâm Bảo tồn Gốm sứ Quốc tế (ICPC) đang tìm kiếm các họa tiết trong một số bức tranh khảm cổ. Theo định nghĩa của ICPC, một bức tranh khảm là một lưới hình chữ nhật mà mỗi ô của lưới chứa một viên gạch có màu. Một họa tiết giống như một bức tranh khảm nhưng một số ô của lưới có thể để trống. Hình dưới đây là họa tiết (bên trái) và bức tranh khảm (bên phải) của ví dụ 1: số trong mỗi ô là màu của viên gạch, là ô trống, mỗi màu được tô một màu riêng.
grid 1 0 0 1 highlight red 1,1 2,2
grid 1 2 1 2 2 1 1 1 2 2 1 3 highlight red 1,1 1,3 2,2 2,3 2,4 3,3 highlight teal 1,2 1,4 2,1 3,1 3,2 highlight orange 3,4
Các hàng của một bức tranh khảm kích thước được đánh số từ đến từ trên xuống dưới, các cột được đánh số từ đến từ trái sang phải.
Một lưới con hình chữ nhật liên tục của bức tranh khảm khớp với họa tiết nếu mọi viên gạch của họa tiết trùng màu với viên gạch tương ứng của lưới con. Chính xác hơn, một họa tiết kích thước xuất hiện trong bức tranh khảm kích thước tại vị trí nếu với mọi , , viên gạch tồn tại trong bức tranh khảm, và hoặc ô của họa tiết để trống, hoặc viên gạch tại của họa tiết có cùng màu với viên gạch tại của bức tranh khảm.
Cho toàn bộ họa tiết và bức tranh khảm, hãy tìm tất cả các vị trí xuất hiện của họa tiết trong bức tranh khảm.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên và (): số hàng và số cột của họa tiết.
- dòng tiếp theo, mỗi dòng chứa số nguyên trong đoạn : màu của họa tiết tại vị trí đó. Giá trị biểu thị ô trống.
- Dòng tiếp theo chứa hai số nguyên và (): số hàng và số cột của bức tranh khảm.
- dòng tiếp theo, mỗi dòng chứa số nguyên trong đoạn : màu của bức tranh khảm tại vị trí đó.
Dữ liệu ra
- Dòng đầu tiên in : tổng số vị trí khớp.
- Tiếp theo in dòng, mỗi dòng có dạng
r c, trong đó là hàng và là cột của viên gạch trên cùng bên trái của vị trí khớp. Sắp xếp các vị trí khớp theo tăng dần, nếu bằng nhau thì theo tăng dần.
Ràng buộc
- .
- Màu trong họa tiết thuộc ( là ô trống), màu trong bức tranh khảm thuộc .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 2 1 0 0 1 3 4 1 2 1 2 2 1 1 1 2 2 1 3 |
3 1 1 1 3 2 2 |
Họa tiết yêu cầu hai ô chéo và đều có màu . Các vị trí , , thỏa mãn. Vị trí không khớp vì ô có màu . Không có vị trí nào ở cột vì họa tiết sẽ vượt ra ngoài bức tranh khảm. |
| 1 3 5 0 5 2 2 5 5 5 5 |
0 | Họa tiết rộng cột, bức tranh khảm chỉ có cột nên không có vị trí nào (ô trống cũng phải nằm trong bức tranh khảm). |
Bình luận