P6397: 论文指数 III
传统题
1.000s
时间限制
256MB
内存限制
0 提交
0 解决
【题目描述】
Bessie
是一位忙碌的计算机科学研究生。然而，即使是研究生也需要交友。因此，Farmer John 开设了一片草地，目的是为了帮助 Bessie 与其他奶牛建立持久的友谊。
Farmer John
的草地可以被看做是由正方形方格组成的巨大二维方阵（想象一个巨大的棋盘）。每个方格用如下字符标记：
C
，如果这个方格中有一头奶牛。
G
，如果这个方格中有草。
.
，如果这个方格既没有奶牛也没有草。
对于两头想要成为朋友的奶牛，她们必须选择在一个与她们均水平或竖直方向上相邻的有草方格见面。在这个过程中，她们会在这个有草方格中吃草，所以之后的奶牛不能再使用这个方格作为见面地点。一头奶牛可以与多头其他奶牛成为朋友，但是同一对奶牛不能见面并成为朋友多于一次。
Farmer John
希望有许多奶牛可以见面并成为朋友。请求出当这一活动结束时在奶牛之间可以建立的朋友关系的最大数量。
输入格式（从终端 /
标准输入读入）：
输入的第一行包含 N
和 M（1≤N,M≤1000）。
以下 N
行每行包含一个由 M 个字符组成的字符串，表示这个草地。
输出格式（输出至终端 /
标准输出）：
输出在这一活动结束时在奶牛之间可以建立的朋友关系的最大数量。
输入样例：
4 5
.CGGC
.CGCG
CGCG.
.CC.C
输出样例：
4
如果我们用坐标 (i,j)
标记第 i 行第 j 列的奶牛，则在这个样例中于 (1,2)、(1,5)、(2,2)、(2,4)、(3,1)、(3,3)、(4,2)、(4,3) 以及 (4,5) 存在奶牛。一种使四对奶牛成为朋友的方式如下：
位于 (2,2)
和 (3,3) 的奶牛于 (3,2) 一起吃草。
位于 (2,2)
和 (2,4) 的奶牛于 (2,3)一起吃草。
位于 (2,4)
和 (3,3) 的奶牛于 (3,4)一起吃草。
位于 (2,4)
和 (1,5) 的奶牛于 (2,5)一起吃草。
测试点性质：
测试点 2-4
满足 N=2。
测试点 5-12
没有额外限制。
供题：Benjamin Qi
【输入】
输入的第一行包含 N 和 M（1≤N,M≤1000）。
以下 N 行每行包含一个由 M 个字符组成的字符串，表示这个草地。
【输出】
输出在这一活动结束时在奶牛之间可以建立的朋友关系的最大数量。
【样例输入】复制
4 5
.CGGC
.CGCG
CGCG.
.CC.C
【提示】
如果我们用坐标 (i,j) 标记第 i 行第 j 列的奶牛，则在这个样例中于 (1,2)、(1,5)、(2,2)、(2,4)、(3,1)、(3,3)、(4,2)、(4,3) 以及 (4,5) 存在奶牛。一种使四对奶牛成为朋友的方式如下：
位于 (2,2) 和 (3,3) 的奶牛于 (3,2) 一起吃草。
位于 (2,2) 和 (2,4) 的奶牛于 (2,3)一起吃草。
位于 (2,4) 和 (3,3) 的奶牛于 (3,4)一起吃草。
位于 (2,4) 和 (1,5) 的奶牛于 (2,5)一起吃草。
测试点性质：
测试点 2-4 满足 N=2。
测试点 5-12 没有额外限制。