Đếm Vùng Nhà Trọ Phố Cổ

Mô tả

Phường cổ trong khu phố tăng vọt nhà trọ dọc các con ngõ nhỏ. Lưới bản đồ phường được thể hiện bằng ma trận $R$ hàng và $C$ cột, mỗi ô mang một trong hai trạng thái: 1 nếu ô đó là nhà trỏ, hoặc 0 nếu là đất trống, tường rào hay đường lớn ngăn cách. Hai ô nhà trỏ được xem là cùng một cụm liên thông nếu một người có thể di chuyển qua các ô nhà trỏ kề cạnh (trên dưới trái phải) mà không cần bước qua ô đất trống.

Đội phòng cháy chữa cháy cần biết toàn bộ phường có bao nhiêu cụm nhà trỏ độc lập, và mỗi cụm chứa số lượng nhà (số ô bằng 1) là bao nhiêu, để ưu tiên kiểm tra các cụm cô lập lớn nhất trước — vì một cụm càng đông mà không nối được ra đường lớn thì nguy cơ kẹt người khi có hỏa hoạn càng cao.

Đầu vào

• Dòng đầu chứa hai số nguyên $R$ và $C$ $(1 \le R, C \le 100)$.
• $R$ dòng tiếp theo, mỗi dòng chứa $C$ số nguyên bằng 0 hoặc 1, mô tả ma trận bản đồ.

Đầu ra

• Dòng đầu ghi số nguyên $K$ — số cụm nhà trỏ liên thông.
• Dòng thứ hai ghi $K$ số nguyên là số lượng nhà của từng cụm, sắp xếp giảm dần, cách nhau bởi một khoảng trắng.

Ràng buộc

• $1 \le R, C \le 100$, tổng số ô không vượt quá $10\,000$.
• Mọi ô chỉ mang giá trị 0 hoặc 1.
• Nếu không có nhà trỏ nào trong phường, xuất 0 trên dòng đầu và dòng thứ hai để trống (chỉ chứa ký tự xuống dòng).

Ví dụ

Ví dụ 1

Input:

4 5 1 1 0 0 1 0 1 0 1 1 0 0 0 0 0 1 0 1 1 1

Output:

4 3 3 3 1

Giải thích:

• Cụm 1 (góc trái trên) gồm ô $(1,1)$, $(1,2)$, $(2,2)$ — 3 ô.
• Cụm 2 (góc phải trên) gồm ô $(1,5)$, , — 3 ô.

(Nhận xét: từng bước quét từng ô, khi gặp ô 1 chưa thăm thì lan rộng theo bốn hướng kề cạnh để gom toàn bộ ô cùng cụm, rồi đếm số ô trong cụm đó.)