2001 - ĐẾM SỐ Ô VUÔNG (DÀNH CHO HỌC SINH THCS VÀ THPT)CHO MỘT B...

Bài 59/2001 - Đếm số ô vuông

(Dành cho học sinh THCS và THPT)

Cho một bảng vuông gồm NxN điểm nằm trên các mắt lưới ô vuông. Các điểm kề nhau trên một hàng hay

một cột có thể được nối với nhau bằng một đoạn thẳng hoặc không được nối. Các đoạn đó sẽ tạo ra các ô

vuông trên bảng. Ví dụ với bảng sau đây thì n = 4 và có 3 ô vuông:

Trên mỗi hàng có thể có nhiều nhất n-1 đoạn thẳng nằm ngang và có tất cả n hàng như vậy. Tương tự như

vậy có tất cả n-1 hàng các đoạn thẳng nằm dọc và trên mỗi hàng có thể có nhiều nhất n đoạn.

Để mô tả người ta dùng hai mảng nhị phân: một mảng ghi các đoạn nằm ngang kích thước n x (n-1), và một

mảng ghi các đoạn nằm dọc kích thước (n-1) xn. Trong mảng, số 1 dùng để mô tả đoạn thẳng nối giữa 2

điểm, còn số 0 miêu tả giữa hai điểm không có đoạn thẳng nối. Trong ví dụ trên thì ma trận "ngang" là:

và ma trận "dọc" là:

1 0 1

 

 

1 1 1 0

1 0 0

1 1 0 1

1 1 1

0 1 1 0

1 1 0

 

Cho trước ma trận "ngang" và ma trận "dọc", dữ liệu nhập từ các tệp văn bản có tên là NGANG.INP và

DOC.INP. Hãy lập trình đếm số các ô vuông trên bảng.