BÀI TOÁN Ô VUÔNG
Thứ Năm, 25 tháng 6, 2015
BÀI 2: Cho
một bảng chữ nhật gồm m x n điểm ( m hàng ngang, n hàng đứng) nằm trên các mắt
lưới ô vuông. Các điểm liền kề trên cùng một hàng hoặc một cột có thể có nối
với nhau bởi một đoạn thẳng có kích thước bằng 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
|
0
|
0
|
0
|
1
|
1
|
1
|
1
|
0
|
1
|
0
|
0
|
|
|
|
|
1
|
1
|
1
|
0
|
0
|
1
|
1
|
0
|
0
|
0
|
0
|
1
|
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
code pascal hay
All comments [ 0 ]
Your comments