Elearning CodePath – CTP Online Judge

Vết dầu loang

DAULOANG

🟢 Hard #Graph #BFS/DFS #Interval

### 📌 Thông tin chung

### 📝 Bài toán

Một tai nạn hàng hải đã khiến dầu tràn ra biển. Để đánh giá mức độ nghiêm trọng của thảm họa, người ta phân tích các hình ảnh chụp từ vệ tinh và chuyển chúng thành một bản đồ lưới nhị phân kích thước N x M. Trên bản đồ này:
- Số 1 đại diện cho ô nước bị nhiễm dầu.
- Số 0 đại diện cho ô nước sạch.

Một vết dầu loang được định nghĩa là một nhóm các ô nhiễm dầu (số 1) có thể kết nối với nhau bằng cách di chuyển qua các cạnh chung (lên, xuống, trái, hoặc phải).

Yêu cầu: Hãy viết chương trình đếm tổng số vết dầu loang riêng biệt và thống kê số lượng vết loang theo từng kích thước.

### 📥 Định dạng Đầu vào

Dữ liệu vào từ file DAULOANG.INP:
- Dòng đầu tiên chứa hai số nguyên N và M là kích thước của bản đồ.
- N dòng tiếp theo, mỗi dòng chứa M số 0 hoặc 1, các số cách nhau bởi dấu cách.

### 📤 Định dạng Đầu ra

Ghi ra file DAULOANG.OUT:
- Dòng đầu tiên ghi một số nguyên là tổng số vết dầu loang tìm được.
- Các dòng tiếp theo, mỗi dòng ghi hai số nguyên S và C, cho biết có C vết loang với kích thước là S. Các dòng này phải được sắp xếp theo thứ tự kích thước S tăng dần.

### ✨ Ví dụ

| Input (DAULOANG.INP) | Output (DAULOANG.OUT) |
| :--- | :--- |
| 5 5 1 1 1 0 0 1 1 0 0 1 0 0 0 1 1 1 0 0 0 0 0 1 1 1 0 | 4 1 1 3 2 5 1 |

### 🏷 Subtasks

| Subtask | Ràng buộc | Tỷ lệ điểm |
| :--- | :--- | :--- |
| 1 | N, M <= 50 | 40% |
| 2 | N, M <= 250 | 60% |

✅ Đã AC: 0 / 10 submissions