Vùng ngập

Xem dạng PDF

Gửi bài giải

Điểm: 1,00 (OI)
Giới hạn thời gian: 2.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Dạng bài

Sau 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

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.