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ò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) - 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ụ:
Input
10 10
1 1 0 0 0 1 0 0 0 0
1 1 0 1 1 1 0 0 0 0
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 1 1 1 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
Output
5
3
1
Ở đây mình vẫn chưa hiểu ở dòng 1 và 2 cũng có các hình số 1 như mình khoanh đỏ mà sao lại không tính.
Và mình đã tính tìm thành phần liên thông toàn 1 thì được nhưng còn trường hợp có số 0 trong lòng HCN thì chưa biết làm ntn, Các bạn chỉ giúp. Cám ơn nhiều
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?