NC222429. [USACOOPEN2021B]AcowdemiaIII
描述
Farmer John's pasture can be regarded as a large 2D grid of square "cells" (picture a huge chess board). Each cell is labeled with:
For two distinct cows to become friends, the cows must choose to meet at a grass-covered square that is directly horizontally or vertically adjacent to both of them. During the process, they eat the grass in the grass-covered square, so future pairs of cows cannot use that square as a meeting point. The same cow may become friends with more than one other cow, but no pair of cows may meet and become friends more than once.
Farmer John is hoping that numerous pairs of cows will meet and become friends over time. Please determine the maximum number of new friendships between distinct pairs of cows that can possibly be created by the end of this experience.
输入描述
The first line contains N and M (N,M≤1000).The next N lines each contain a string of M characters, describing the pasture.
输出描述
Count the maximum number of pairs of cows that can become friends by the end of the experience.
示例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 at (1,2), (1,5), (2,2), (2,4), (3,1), (3,3), (4,2), (4,3), and (4,5). One way for four pairs of cows to become friends is as follows: