BÀI TỐN Ơ VUƠNGCHO MỘT BẢNG CHỮ NHẬT GỒM M X N ĐIỂM ( M HÀNG NGANG, N...

1.

Trên mỗi hàng cĩ nhiều nhất n-1 đoạn thẳng nằm ngang nối các điểm liền nhau, trên mỗi cột cĩ nhiều nhất

là m-1 đoạn thẳng thẳng đứng nối các điểm liền nhau. Các đoạn liền kề nhau cĩ thể sẽ tạo ra các ơ vuơng

trên bảng (chỉ quan tâm các ơ vuơng cĩ độ dài cạnh bằng 1). Xem hình dưới:

Với bảng trên ta cĩ 4 hàng ngang (mỗi hàng 5 điểm) và 5 hàng đứng (mỗi hàng 4 điểm). Các đoạn thẳng nối

chúng tạo nên 3 ơ vuơng.

Để mơ tả bảng người ta dùng hai mảng nhị phân: một mảng diễn tả các đoạn thẳng nằm ngang, một mảng

diễn tả các đoạn thẳng thẳng đứng.

Trong các mảng, số 1 diễn tả cĩ đoạn thẳng nối hai điểm liên tiếp, số 0 diễn tả khơng cĩ đoạn thẳng nối hai

điểm.

Trong hình vẽ trên, (bảng cĩ 4x5 điểm) thì ta cĩ hai mảng sau:

Ngang Dọc

1 0 1 0

1 1 1 0 0

1 0 0 0

1 1 0 0 0

1 1 1 1

0 1 1 0 0

0 1 0 0

Nhiệm vụ :

Lập trình đếm số các ơ

vuơng cĩ cạnh dộ dài bằng 1 tạo bởi các đoạn nối cĩ trên bảng đã cho.

Dữ liệu vào: gồm ba tập tin

Kthuoc.inp: gồm 2 số nguyên dương (nhỏ hơn 100) lần lượt là m, n. Hai số cách nhau một khoảng trắng

Ngang.inp và Doc.inp ( như mơ tả ở phần trên). Hai số liền nhau cách nhau một khoảng trắng.

Dữ liệu ra : Xuất ra màn hình số ơ vuơng cĩ trên bảng đã cho.

Ví dụ :

Kthuoc.inp:

4 5

Ngang.inp và Doc.inp chứa nội dung như hai bảng trên.

Xuất ra màn hình : 3

Lưu ý: Chỉ tính các ơ vuơng cĩ độ dài cạnh bằng 1

Yêu cầu kỹ thuật :

+ Khơng cần kiểm tra dữ liệu nhập

+ Bài làm của thí sinh lưu trên tập tin Bailam2.pas

HẾT

MỘT SỐ BỘ TEST THAM KHẢO