#1083 · Cặp nhà vui vẻ - FNHOUSES

Cho 1 mảnh đất M hàng và N cột. Mỗi ô (i, j) trên đó có thể có 1 ngôi nhà hoặc không có gì cả.

Tại đây, 2 ngôi nhà được gọi là cặp nhà vui vẻ nếu 2 ô đất của chúng có chung cạnh hoặc chung góc với nhau. Mảnh đất càng có nhiều cặp nhà vui vẻ thì càng đắt giá. Chính vì vậy, tổ chức Hutech Coder quyết định xây thêm đúng 1 ngôi nhà trên bất kì ô trống nào trên mảng đất đó sao cho số lượng cặp nhà vui vẻ nhiều nhất. Nếu không còn ô đất nào trống thì tổ chức sẽ không xây thêm nhà.

Hãy giúp tổ chức Hutech Coder tìm số lượng cặp nhà vui vẻ lớn nhất.

• Dòng đầu tiên gồm 2 số nguyên dương M, N là kích thước mảnh đất (1 \leq M, N \leq 10^3).
• M dòng tiếp theo, mỗi dòng chứa N ký tự, "." nếu ô đất trống và "#" nếu ô đất đó có nhà.

In ra 1 số duy nhất là số lượng cặp nhà vui vẻ lớn nhất.