Acowdemia III

Bessie는 바쁜 컴퓨터과학 대학원생이다. 하지만 대학원생에게도 친구는 필요하다. 그래서 Farmer John은 Bessie와 다른 소들이 오래가는 우정을 맺도록 돕기 위한 목적으로 목초지를 하나 열었다.

Farmer John의 목초지는 정사각형 "칸"들로 이루어진 거대한 2차원 격자로 볼 수 있다(거대한 체스판을 떠올리면 된다). 각 칸에는 다음 중 하나가 적혀 있다.

• C: 칸에 소가 있다.
• G: 칸에 풀이 있다.
• .: 칸에 소도 풀도 없다.

서로 다른 두 소가 친구가 되려면, 두 소 모두와 가로 또는 세로로 인접한 풀이 있는 칸에서 만나기로 해야 한다. 만나는 동안 두 소는 그 풀이 있는 칸의 풀을 먹어버리므로, 이후 다른 소 쌍은 그 칸을 만남의 장소로 쓸 수 없다. 같은 소가 둘 이상의 다른 소와 친구가 될 수 있지만, 같은 두 소가 두 번 이상 만나 친구가 될 수는 없다.

Farmer John은 시간이 지나면서 많은 소 쌍이 만나 친구가 되기를 바란다. 이 경험이 끝날 때까지 서로 다른 소 쌍 사이에 만들어질 수 있는 새로운 친구 관계의 최대 개수를 구하시오.

첫째 줄에 $N$과 $M$이 주어진다. ($N,M \leq 1000$)

다음 $N$개의 줄에는 목초지를 나타내는 길이 $M$의 문자열이 각각 주어진다.

이 경험이 끝날 때까지 친구가 될 수 있는 소 쌍의 최대 개수를 출력한다.

$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)$의 풀을 먹는다.