Farmer John opened a pasture to help Besie and her friends.
The PD pasture can be viewed as a large 2D grid of square cells. Each cell is labeled like this:
- C if the cell contains a cow
- G if the cell contains grass
- . if there is no cow or grass in the cell
In order for two different cows to become friends, the cows must meet in a cell with grass that is horizontally or vertically adjacent to each of them. During this process, they eat the grass in that cell, so another pair of cows can no longer use that cell as a meeting place. Any cow can befriend more than one other cow, but no pair of cows can meet and become friends more than once.
The FD hopes that many pairs of cows will become friends. Determine the maximum number of pairs of cows that can become friends.
INPUT FORMAT:
The first line contains N and M.
Each of the next N lines contains M characters describing a pasture.
OUTPUT FORMAT:
Determine the maximum number of pairs of cows that can become friends.
| # |
Input |
Output |
| 1 |
4 5
.CGGC
.CGCG
CGCG.
.CC.C
|
4 |
If we label the cow in row i and column j with coordinates (i,j), then in this example there are cows in (1,2), (1,5), (2,2), (2,4), (3 ,1), (3,3), (4,2), (4,3), and (4,5). One way for 4 cows to become friends is this:
Cows from (2,2) and (3,3) eat grass in (3,2).
Cows from (2,2) and (2,4) eat grass in (2,3).
Cows from (2,4) and (3,3) eat grass in (3,4).
Cows in (2,4) and (1,5) eat grass in (2,5).