Задача: Acowdemia III

Фермер Джон открыл пастбище с целью помочь Беси и её друзьям.
Пастбище ФД можно рассматривать как большую 2D-решётку квадратных ячеек. Каждая ячейка помечена таким образом:

• C если в ячейке корова
• G если в ячейке трава
• . если в ячейке нет ни коровы, ни травы

Для того, чтобы две различные коровы стали друзьями, коровы должны встретиться в ячейке с травой, которая горизонтально или вертикально соседствует с каждой из них. Во время этого процесса они съедают траву в этой ячейке, поэтому другая пара коров уже не сможет использовать эту ячейку как место встречи. Любая корова может подружиться более чем с одной другой коровой, но никакая пара коров не может встретиться и стать друзьями более одного раза.

ФД надеется, что много пар коров станут друзьями. Определите максимальное количество пар коров, которые могут стать друзьями.

ФОРМАТ ВВОДА:
Первая строка содержит N и M (2 ≤ N,M ≤ 1000).
Каждая из следующих N строк содержит M символов, описывая пастбище.

ФОРМАТ ВЫВОДА:
Определите максимальное количество пар коров, которые могут стать друзьями.
 

№	Входные данные	Выходные данные
1	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), and (4,5). Один из способов, чтобы 4 коровы стали друзьями таков:

Коровы из (2,2) и (3,3) едят траву в (3,2).
Коровы из (2,2) и (2,4) едят траву в (2,3).
Коровы из (2,4) и (3,3) едят траву в (3,4).
Коровы из (2,4) и (1,5) едят траву в (2,5).

           

Ваш ответ: