#M0059. 细菌游戏
细菌游戏
题目描述
小 Z 正在玩一个细菌游戏,游戏中是一个由正方形方格组成的巨大二维方阵(想象一个巨大的棋盘)。每个方格用如下字符标记:
C
,代表着这个格子是一个细菌。G
,代表着这个格子是一个营养物质。.
,代表着这个格子又没有细菌,又没有营养物质。
现在,这些细菌打算要进行两两交友,但是他们必须要选择在一个与他们均水平或竖直方向上相邻的有营养物质的方格汇合。在这个过程中,他们会在这个方格中汲取营养物质,而这个方格的营养物质一旦被吃完,则会变成一个普通格子,所以之后的其他细菌不能再使用这个方格作为见面地点。一个细菌可以与其他多个细菌成为朋友,但是同一对细菌不能见面并成为朋友多于一次。
小 Z 希望有许多细菌可以成为朋友。请求出当这一游戏结束时在细菌之间可以建立的朋友关系的最大数量。
输入格式
输入的第一行包含 和 。
以下 行每行包含一个由 个字符组成的字符串,表示这个方阵。
输出格式
输出在这一游戏结束时在细菌之间可以建立的朋友关系的最大数量。
输入输出样例
4 5
.CGGC
.CGCG
CGCG.
.CC.C
4
提示
【样例解释】
如果我们用坐标 标记第 行第 列的细菌,则在这个样例中于 (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 满足 。
- 测试点 5-12 没有额外限制。