Lấp hồ
Đề bài
Mô tả
Cho bản đồ hình chữ nhật gồm hàng, cột. Mỗi ô là đất (#) hoặc nước (.). Hai ô nước thông nhau nếu chúng chung một cạnh (chỉ đi lên, xuống, trái, phải; hai ô chỉ chạm nhau ở góc thì không thông nhau).
Một hồ là một vùng nước liên thông (lớn nhất có thể) không chứa ô nào nằm ở mép bản đồ (hàng đầu, hàng cuối, cột đầu hoặc cột cuối). Nói cách khác, nước trong hồ không thể chảy ra ngoài bản đồ.
Người ta lấp đầy mọi hồ bằng đất. Hãy cho biết số hồ, tổng số ô bị lấp và bản đồ sau khi lấp.
Dữ liệu vào
- Dòng đầu chứa hai số nguyên .
- dòng tiếp theo, mỗi dòng là một xâu độ dài chỉ gồm
#và..
Dữ liệu ra
- Dòng đầu in hai số nguyên: số hồ và tổng số ô bị lấp.
- dòng tiếp theo in bản đồ sau khi lấp.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 7 8 #######. #..#..#. #..#.##. ####.... #.#.###. #.#.#.#. ###.###. |
3 7 #######. ####..#. ####.##. ####.... ###.###. ###.###. ###.###. |
Ba hồ: khối ở góc trên trái, hai ô ở cột 2 (hàng 5, 6) và một ô ở hàng 6 cột 6. Vùng ba ô ở hàng 2, 3 không phải hồ vì nó thông xuống hàng 4 rồi ra mép phải. Vùng nước ở cột 4 (hàng 5 đến 7) chạm mép dưới nên cũng không phải hồ. |
| 5 5 ##### #...# #.#.# #...# ##.## |
0 0 ##### #...# #.#.# #...# ##.## |
Vùng nước bao quanh ô đất ở giữa thông ra mép dưới qua ô ở hàng 5 cột 3, nên không có hồ nào. |
Bình luận