trang chủ / đề bài / dhbb26_dx34_11_b

Tìm đất xây biệt thự

Đề bài

Mô tả

Bản đồ của thành phố nơi Nam sinh sống được mô tả là một bảng chữ nhật có kích thước m1×m2 (1≤m1·m2≤200000) gồm các chữ cái tiếng Anh in thường ('a' … 'z') thể hiện địa hình của vùng đất. Nam muốn chọn một khu đất có địa hình phù hợp để xây dựng biệt thự. Địa hình khu đất này được mô tả là một hình có kích thước n1×n2 gồm các chữ cái in thường như mô tả của bản đồ.

Yêu cầu: Tìm tất cả các khu đất Nam có thể dùng để xây biệt thự trong thành phố, tức là mọi vị trí (r,c) sao cho hình chữ nhật n1×n2 của bản đồ có góc trên bên trái ở dòng r, cột c trùng khớp hoàn toàn với địa hình khu đất.

Dữ liệu vào

  • Dòng đầu ghi hai số nguyên n1,n2 (1≤n1,n2≤100).
  • n1 dòng tiếp theo, mỗi dòng ghi n2 chữ cái mô tả địa hình khu đất Nam cần chọn.
  • Dòng tiếp theo ghi hai số nguyên m1,m2 (1≤m1,m2≤2000).
  • m1 dòng tiếp theo, mỗi dòng ghi m2 chữ cái mô tả bản đồ thành phố.

Dữ liệu ra

Mỗi dòng ghi vị trí phía trên bên trái của một khu đất phù hợp trong bản đồ, theo dạng (r,c) với r là chỉ số dòng, c là chỉ số cột (đánh số từ 1). Các vị trí ghi theo thứ tự từ điển tăng dần: tăng dần theo r, cùng r thì tăng dần theo c. Nếu không tìm thấy khu đất phù hợp ghi số 0.

Ràng buộc

  • 1≤n1,n2≤100.
  • 1≤m1,m2≤2000, m1·m2≤200000.

Subtasks

  • Subtask 1 (30% số điểm): m1,m2≤20.
  • Subtask 2 (70% số điểm): Không có ràng buộc gì thêm.

Ví dụ

Input Output Giải thích
3 3
aba
bab
aba
7 6
aababa
ababab
bababa
ababab
ababab
bababa
ababab
(1,2)
(1,4)
(2,1)
(2,3)
(5,1)
(5,3)
Có 6 khu đất phù hợp.
1 1
a
2 2
bb
cc
0 Bản đồ không có chữ 'a'.

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