ĐẾM HÌNH CHỮ NHẬT CHO MỘT MA TRẬN A KÍCH THƯỚC MXN, CÁC PHẦN TỬ A[I,J...

Bài 4: Đếm hình chữ nhật

Cho một ma trận A kích thước MxN, các phần tử A[i,j] bằng 0 hoặc bằng 1, các ô

số 1 liền cạnh nhau khép kín có thể tạo thành hình chữ nhật đậm đặc – toàn là số 1 hoặc

hình chữ nhật bị rỗng ở trong (ở trong lòng hình chữ nhật có các số 0). Hãy viết chương

trình đếm xem có bao nhiêu hình chữ nhật như trên, trong đó có bao nhiêu hình chữ nhật

đậm đặc (loại 1) và bao nhiêu hình chữ nhật rỗng ở trong có duy nhất một hình chữ nhật

chứa toàn số 0 (loại 2)?

Dữ liệu vào trong file văn bản “Bai4.inp” có dạng:

- Dòng đầu chứa 2 số M, N (1<M,N<=200)

- M dòng tiếp theo thể hiện ma trận A.

(mỗi số cách nhau một dấu cách)

Kết quả cho ra file văn bản “Bai4.out” có dạng:

- Dòng đầu chứa số lượng các loại hình chữ nhật

- Dòng thứ hai chứa số lượng các hình chữ nhật loại 1

- Dòng thứ ba chứa số lượng các hình chữ nhật loại 2.

Ví dụ:

Bai4.inp Bai4.out

5

10 10

1 1 0 0 0 1 0 0 0 0

3

1 1 0 1 1 1 0 0 0 0

1

0 0 0 0 0 0 1 1 0 0

0 0 1 1 1 1 0 0 0 0

0 0 1 0 0 1 0 0 0 0

0 0 0 0 0 0 0 0 0 0

1 0 0 1 1 1 1 1 1 0

0 0 0 1 0 1 1 0 1 0

0 0 0 1 1 1 1 1 1 0

( Có 50% số test M,N<=100)