trang chủ / đề bài / icpcwf21_g

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, 0 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 rq×cq được đánh số từ 1 đến rq từ trên xuống dưới, các cột được đánh số từ 1 đến cq 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 rp×cp xuất hiện trong bức tranh khảm kích thước rq×cq tại vị trí (r,c) nếu với mọi 1≤i≤rp, 1≤j≤cp, viên gạch (r+i−1,c+j−1) tồn tại trong bức tranh khảm, và hoặc ô (i,j) của họa tiết để trống, hoặc viên gạch tại (i,j) của họa tiết có cùng màu với viên gạch tại (r+i−1,c+j−1) 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 rp và cp (1≤rp,cp≤1000): số hàng và số cột của họa tiết.
  • rp dòng tiếp theo, mỗi dòng chứa cp số nguyên trong đoạn [0,100]: màu của họa tiết tại vị trí đó. Giá trị 0 biểu thị ô trống.
  • Dòng tiếp theo chứa hai số nguyên rq và cq (1≤rq,cq≤1000): số hàng và số cột của bức tranh khảm.
  • rq dòng tiếp theo, mỗi dòng chứa cq số nguyên trong đoạn [1,100]: màu của bức tranh khảm tại vị trí đó.

Dữ liệu ra

  • Dòng đầu tiên in k: tổng số vị trí khớp.
  • Tiếp theo in k dòng, mỗi dòng có dạng r c, trong đó r là hàng và c 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 r tăng dần, nếu r bằng nhau thì theo c tăng dần.

Ràng buộc

  • 1≤rp,cp,rq,cq≤1000.
  • Màu trong họa tiết thuộc [0,100] (0 là ô trống), màu trong bức tranh khảm thuộc [1,100].

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 (1,1) và (2,2) đều có màu 1. Các vị trí (1,1), (1,3), (2,2) thỏa mãn. Vị trí (1,2) không khớp vì ô (1,2) có màu 2. Không có vị trí nào ở cột 4 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 3 cột, bức tranh khảm chỉ có 2 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

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

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0