Vùng ngập
Xem dạng PDFSau trận mưa lớn, câu lạc bộ Flycam chụp ảnh khuôn viên trường từ trên cao rồi chia bức ảnh thành một lưới ô vuông gồm ~n~ hàng và ~m~ cột. Mỗi ô được đánh dấu bằng một ký tự: # nếu ô đó đang bị ngập nước, . nếu ô đó khô ráo.
Hai ô được gọi là kề nhau nếu chúng chung một cạnh (ô ngay phía trên, dưới, trái hoặc phải); hai ô chỉ chạm nhau ở góc thì không kề nhau. Một vùng ngập là một nhóm ô ngập mà từ một ô bất kỳ của nhóm có thể đi tới mọi ô khác của nhóm bằng cách lần lượt bước sang ô ngập kề nhau, đồng thời không thể thêm ô ngập nào khác vào nhóm mà vẫn giữ được tính chất đó. Diện tích của một vùng ngập là số ô của nó.
Yêu cầu
Hãy đếm số vùng ngập và tìm diện tích của vùng ngập lớn nhất để nhà trường bố trí máy bơm.
Dữ liệu vào
- Dòng thứ nhất chứa hai số nguyên ~n~ và ~m~;
- ~n~ dòng tiếp theo, mỗi dòng chứa đúng ~m~ ký tự liền nhau, mỗi ký tự là
#hoặc., mô tả một hàng của lưới.
Kết quả ra
Ghi ra trên một dòng hai số nguyên cách nhau một dấu cách: số vùng ngập và diện tích của vùng ngập lớn nhất. Nếu lưới không có ô ngập nào, ghi ra 0 0.
Ràng buộc
~1 \le n, m \le 1000~.
- Subtask 1 (20% số điểm – test 01–04): ~n = 1~;
- Subtask 2 (30% số điểm – test 05–10): ~n, m \le 50~;
- Subtask 3 (50% số điểm – test 11–20): không có ràng buộc bổ sung.
Ví dụ
Dữ liệu vào mẫu 1
5 6
##..#.
#...#.
.#..##
..#...
.##...
Kết quả ra mẫu 1
4 4
Giải thích
Ký hiệu ~(i, j)~ là ô ở hàng ~i~, cột ~j~. Có ~4~ vùng ngập: vùng gồm các ô ~(1,1)~, ~(1,2)~, ~(2,1)~ có diện tích ~3~; vùng gồm các ô ~(1,5)~, ~(2,5)~, ~(3,5)~, ~(3,6)~ có diện tích ~4~; vùng chỉ gồm ô ~(3,2)~ có diện tích ~1~; vùng gồm các ô ~(4,3)~, ~(5,2)~, ~(5,3)~ có diện tích ~3~. Ô ~(3,2)~ chỉ chạm góc với các ô ~(2,1)~ và ~(4,3)~ nên tự nó là một vùng.
Bình luận