USACO 2021 - Open - Bronze - Acowdemia III

View as PDF

Submit solution

Points: 0.05 (partial)
Time limit: 0.5s
Memory limit: 256M
Input: stdin
Output: stdout

Suggester:
Problem source:
http://www.usaco.org/index.php?page=viewproblem2&cpid=1133
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Bessie là một sinh viên ngành Khoa học máy tính rất bận bịu. Tuy nhiên, sinh viên cũng cần phải có bạn. Vì vậy, bác nông dân John đã mở một bãi cỏ với mục đích giúp Bessie và những chú bò khác kết bạn với nhau.

Bãi cỏ của bác John có thể được coi là một bảng 2D gồm các ô vuông (như một bàn cờ vua lớn). Mỗi ô được đánh dấu như sau:

  • ~C~ nếu ô đó chứa một chú bò.
  • ~G~ nếu ô đó chứa cỏ.
  • ~.~ nếu ô đó không chứa gì cả.

Để hai chú bò khác nhau có thể trở thành bạn, chúng phải chọn gặp mặt tại một ô chứa cỏ mà nằm cạnh cả hai ô của chúng theo chiều dọc hoặc chiều ngang. Trong quá trình kết bạn, hai chú bò sẽ ăn hết cỏ trên ô này nên trong tương lai không cặp bò nào có thể gặp mặt và kết bạn tại ô đó nữa. Một chú bò có thể kết bạn với nhiều chú bò khác, nhưng không cặp bò nào có thể gặp mặt và trở thành bạn nhiều hơn một lần.

Bác John mong rằng sẽ có nhiều cặp bò gặp mặt và kết bạn với nhau. Hãy đếm số lần kết bạn tối đa có thể xảy ra giữa các cặp bò phân biệt.

Input

Dòng đầu tiên chứa hai số nguyên ~N~ và ~M~ ~(N, M \le 1000)~.

~N~ dòng tiếp theo, mỗi dòng gồm ~M~ kí tự miêu tả bãi cỏ của bác John.

Output

In ra số lượng cặp bò phân biệt tối đa có thể trở thành bạn bè.

Sample Input

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

Sample Output

4

Giải thích, nếu ta đánh dấu chú bò ở hàng ~i~, cột ~j~ với tọa độ ~(i, j)~ thì trong ví dụ này có các chú bò ở các ô ~(1,2)~, ~(1,5)~, ~(2,2)~, ~(2,4)~, ~(3,1)~, ~(3,3)~, ~(4,2)~, ~(4,3)~, và ~(4,5)~. Một cách để 4 cặp bò trở thành bạn bè là:

  • Chú bò ở ô ~(2, 2)~ và chú bò ở ô ~(3, 3)~ gặp mặt tại ô ~(3, 2)~.
  • Chú bò ở ô ~(2, 2)~ và chú bò ở ô ~(2, 4)~ gặp mặt tại ô ~(2, 3)~.
  • Chú bò ở ô ~(2, 4)~ và chú bò ở ô ~(3, 3)~ gặp mặt tại ô ~(3, 4)~.
  • Chú bò ở ô ~(2, 4)~ và chú bò ở ô ~(1, 5)~ gặp mặt tại ô ~(2, 5)~.

Ràng buộc

  • Test 1 là test mẫu
  • Các test 2-4 thỏa mãn ~N = 2~.
  • Các test 5-12 không có thêm ràng buộc gì.

Comments

Please read the guidelines before commenting.


There are no comments at the moment.