Bài 2: Định cư (ghostforest.pas) (7 điểm) (1 giây)

Một nhóm người dân di cư vào một khu rừng gần ngoại ô để sinh sống, tuy muốn lập thành một làng để sống nhưng họ lại không muốn chặt phá cây rừng. Vì khu rừng này trước đây bị 1 phù thủy nguyền rủa, “Khu rừng thật sự đang sống”. Họ muốn định cư xây nhà sao cho không có bất kì một ngôi nhà nào tiếp xúc trực tiếp với 2 cây rừng, vì nếu có từ 2 cây rừng trở lên bao quanh 1 ngôi nhà thì ngôi nhà đó sẽ bị nó nuốt chửng. Mỗi cây rừng được quy định trên 1 diện tích đất và mỗi ngôi nhà cũng vậy.

Yêu cầu: Hãy xác định số ngôi nhà tối đa và số ngôi làng mà người ta có thể xây trên 1 bản đồ cho sẵn, mỗi số cách nhau 1 dấu cách. Quy ước: một làng được hình thành khi tất cả các ngôi nhà được liên kết với nhau.

Dữ liệu vào:

-          Dòng 1: gồm 2 số nguyên N và M (2 <= N,M <= 500).

-          Trong N dòng tiếp theo, mỗi dòng chứa M kí tự cách nhau bởi 1 dấu cách, kí tự “0” tương ứng với ô đất trống và kí tự “1” tương ứng với ô đất có cây rừng.

Dữ liệu ra: Gồm 2 số nguyên là số nhà tối đa có thể xây trên bản đồ và số làng trên bản đồ đó.

Giải thích: có 22 ngôi nhà được xây mà không ngôi nhà nào tiếp xúc trực tiếp với 2 cây rừng và có 2 làng trong mảnh đất này, đồng thời hình thành nên 3 làng.