Đếm Vùng Rừng Ngập Mặn Cà Mau

Mô tả

Chi cục Thủy sản Cà Mau vừa nhận được bản đồ vệ tinh vùng ngập mặn dọc bờ biển. Bản đồ được chia thành một lưới chữ nhật kích thước m × n, mỗi ô mang giá trị 1 nếu là rừng ngập mặn (bao phủ thực sự) và 0 nếu là bùn trống hoặc mặt nước.

Một vùng rừng là tập hợp các ô mang giá trị 1 liên thông với nhau theo 4 hướng (trên, dưới, trái, phải). Các ô chỉ chéo góc không tính là liên thông. Nhiệm vụ của bạn là đếm tổng số vùng rừng ngập mặn xuất hiện trên bản đồ.

Đầu vào

• Dòng 1: hai số nguyên m và n (1 ≤ m, n ≤ 50), số hàng và số cột của lưới.
• m dòng tiếp theo, mỗi dòng chứa n số nguyên 0 hoặc 1 cách nhau bởi khoảng trắng, mô tả bản đồ.

Đầu ra

• Một số nguyên duy nhất: số lượng vùng rừng ngập mặn.

Ràng buộc

• 1 ≤ m, n ≤ 50.
• Mỗi ô chỉ nhận giá trị 0 hoặc 1.
• Tổng số ô không vượt quá 2500.

Ví dụ

Ví dụ 1

Đầu vào:

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

Đầu ra:

4

Giải thích từng bước:

• Vùng 1: hai ô (1,1) và (1,2) — chúng nằm kề nhau theo chiều ngang. Ô (2,1) cũng nối với (1,1) theo chiều dọc, nên cả ba ô { (1,1), (1,2), (2,1) } thuộc cùng một vùng.
• Vùng 2: ba ô { (1,5), (2,4), (2,5) } liên thông với nhau ( (2,4) nối (2,5) theo chiều ngang, (1,5) nối (2,5) theo chiều dọc).
• Vùng 3: ô đơn lẻ (3,3).
• Vùng 4: ô đơn lẻ (4,1) — ô này ở dòng 4, không nối với vùng 1 ở dòng 1 vì giữa chúng toàn ô 0.

Tổng cộng có 4 vùng rừng ngập mặn.

Ví dụ 2

Đầu vào:

3 3 0 0 0 0 0 0 0 0 0

Đầu ra:

0

Giải thích: Toàn bộ bản đồ là bùn trống, không có vùng rừng nào.