P9939 [USACO21OPEN] Acowdemia III B

Bessie is a busy computer science graduate student. However, even graduate students need to make friends. Therefore, Farmer John opened up a pasture with the goal of helping Bessie build lasting friendships with other cows. Farmer John’s pasture can be viewed as a huge 2D grid of square cells (imagine a giant chessboard). Each cell is marked with one of the following characters: - `C`, if there is a cow in this cell. - `G`, if there is grass in this cell. - `.`, if this cell has neither a cow nor grass. For two cows that want to become friends, they must choose a grass cell that is adjacent (horizontally or vertically) to both of them as their meeting place. During this process, they will eat the grass in that cell, so later cows can no longer use that cell as a meeting place. A cow can become friends with multiple other cows, but the same pair of cows cannot meet and become friends more than once. Farmer John wants as many cows as possible to meet and become friends. Compute the maximum number of friendship relationships that can be formed between cows by the time this activity ends.

The first line contains $N$ and $M$ ($1 \le N, M \le 1000$). The next $N$ lines each contain a string of length $M$, describing the pasture.

Output the maximum number of friendship relationships that can be formed between cows by the time this activity ends.

### Sample Explanation 1 If we use coordinates $(i, j)$ to denote the cow in row $i$, column $j$, then in this sample, there are cows at $(1,2)$, $(1,5)$, $(2,2)$, $(2,4)$, $(3,1)$, $(3,3)$, $(4,2)$, $(4,3)$, and $(4,5)$. One way to make four pairs of cows become friends is as follows: - The cows at $(2,2)$ and $(3,3)$ eat grass together at $(3,2)$. - The cows at $(2,2)$ and $(2,4)$ eat grass together at $(2,3)$. - The cows at $(2,4)$ and $(3,3)$ eat grass together at $(3,4)$. - The cows at $(2,4)$ and $(1,5)$ eat grass together at $(2,5)$. ### Test Point Properties - Test points $2-4$ satisfy $N = 2$. - Test points $5-12$ have no additional constraints. Translated by ChatGPT 5