Bessie là một nghiên cứu sinh khoa học máy tính bận rộn. Tuy nhiên, ngay cả nghiên cứu sinh cũng cần bạn bè. Vì vậy, Farmer John đã mở một đồng cỏ với mục đích giúp Bessie và những con bò khác xây dựng tình bạn bền chặt.

Có thể coi đồng cỏ của Farmer John là một lưới hai chiều rộng gồm các ô vuông, giống như một bàn cờ khổng lồ. Mỗi ô được ký hiệu bởi:

• C nếu ô đó có một con bò;
• G nếu ô đó có cỏ;
• . nếu ô đó không có bò lẫn cỏ.

Để hai con bò phân biệt trở thành bạn, chúng phải chọn gặp nhau tại một ô có cỏ kề trực tiếp theo chiều ngang hoặc dọc với cả hai con. Trong quá trình đó, chúng ăn cỏ trong ô này, do đó các cặp bò sau này không thể dùng lại ô này làm điểm gặp. Một con bò có thể kết bạn với nhiều con bò khác, nhưng mỗi cặp bò chỉ có thể gặp nhau và trở thành bạn nhiều nhất một lần.

Farmer John hy vọng sẽ có nhiều cặp bò gặp nhau và trở thành bạn theo thời gian. Hãy xác định số tình bạn mới lớn nhất giữa các cặp bò phân biệt có thể được tạo ra khi hoạt động này kết thúc.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(M\) (\(N,M\le1000\)).

Mỗi dòng trong \(N\) dòng tiếp theo chứa một xâu gồm \(M\) ký tự, mô tả đồng cỏ.

Dữ liệu ra

In số cặp bò lớn nhất có thể trở thành bạn khi hoạt động kết thúc.

Phân nhóm

• Các test 2-4 thỏa mãn \(N=2\).
• Các test 5-12 không có ràng buộc bổ sung.

Ví dụ

4 5
.CGGC
.CGCG
CGCG.
.CC.C

4

Nếu gán cho con bò ở hàng \(i\), cột \(j\) tọa độ \((i,j)\), thì trong ví dụ có các con bò tại \((1,2)\), \((1,5)\), \((2,2)\), \((2,4)\), \((3,1)\), \((3,3)\), \((4,2)\), \((4,3)\) và \((4,5)\). Một cách để bốn cặp bò trở thành bạn là:

• Hai con bò tại \((2,2)\) và \((3,3)\) ăn cỏ tại \((3,2)\).
• Hai con bò tại \((2,2)\) và \((2,4)\) ăn cỏ tại \((2,3)\).
• Hai con bò tại \((2,4)\) và \((3,3)\) ăn cỏ tại \((3,4)\).
• Hai con bò tại \((2,4)\) và \((1,5)\) ăn cỏ tại \((2,5)\).

Nguồn

USACO 2021 US Open, Bronze - Acowdemia III: https://usaco.org/index.php?page=viewproblem2&cpid=1133

Tác giả: Benjamin Qi.