Trang chủ
 
Lớp 9
 
Tin học
 
BÀI TOÁN Ô VUÔNG (4 ĐIỂM) FILE BÀI LÀM
BÀI TOÁN Ô VUÔNG (4 ĐIỂM) FILE BÀI LÀM
Lớp 9
Tin học
Đề thi HSG tin học năm 2013 tỉnh Ninh Bình
Nội dung
Đáp án tham khảo
Bài 3: Bài toán ô vuông (4 điểm) File bài làm: SQUARE.PAS
Cho một bảng chữ nhật gồm m * n điểm (gồm m hàng ngang trên mỗi hàng có
n điểm). 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. Xem hình dưới:
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
Với bảng trên ta có 3 hàng ngang mỗi hàng 5 điểm. Các đoạn thẳng nối chúng
tạo nên 2 ô vuông. Để mô tả bảng người ta dùng hai mảng nhị phân: mảng Ngang
diễn tả các đoạn thẳng nằm ngang, mảng Dọc biểu diễn 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 liên tiếp.
Yêu cầu: Lập trình đếm số lượng các ô vuông mà cạnh có độ 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: SQUARE.INP
+ Dòng đầu tiên gồm 2 số nguyên dương lần lượt là m, n (m, n ≤ 1000). Hai số
cách nhau một khoảng trắng.
+ m dòng tiếp theo diễn tả các đoạn thẳng nằm ngang (như bảng ngang mô tả ở
phần trên). Hai số liền nhau cách nhau một khoảng trắng.
+ m - 1 dòng tiếp theo diễn tả các đoạn thẳng thẳng đứng (như bảng dọc mô tả
ở phần trên). Hai số liền nhau cách nhau một khoảng trắng.
Dữ liệu ra : SQUARE.OUT
+ Số lượng ô vuông có độ dài cạnh bằng 1.
Ví dụ:
SQUARE.INP
SQUARE.OUT
2
3 5
1 0 1 0
1 0 0 0
1 1 1 1
1 1 1 0 0
1 1 0 0 0
Bạn đang xem
bài 3:
-
Đề thi HSG tin học năm 2013 tỉnh Ninh Bình