문제
권수쌤의 지도교수님은 친구를 사귀고 싶어서 학회를 열었습니다.
학회가 열리는 세미나실은 거대한 2차원 정사각형으로 생각할 수 있습니다(거대한 체스판을 상상해봅시다).
각 사각형은 다음 문자로 표시됩니다.
- C, 이 장소에 교수님이 있는 경우.
- G, 이 장소에 대학원생이 있는 경우.
- ., 이 장소에 대학원생도 교수님도 없는 경우.
두 명의 교수들이 친구가 되기 위해서는 멀리가진 못하고 그저 두 명 모두에게 수평 또는 수직으로 인접한 장소에서 만나기를 바랍니다.
교수님들이 친구가 되기 위해서는 함께 합심하여 대학원생을 괴롭혀야 합니다.
이 과정에서 그들은 대학원생을 괴롭혀서 쫓아낼 것이므로 나중에 다른 교수님들은
더 이상 대학원생이 존재하지 않는 해당 장소를 친구가 되는 장소로 사용할 수 없습니다.
교수님은 다른 많은 교수들과 친구가 될 수 있지만 같은 쌍의 교수님들은 한 번 이상 만나서 친구가 될 수 없습니다.
교수님은 많은 교수를 만나고 친구가 되기를 희망합니다.
이 세미나가 종료되면 교수들 사이에 형성할 수 있는 최대 우정 수를 계산하는 프로그램을 작성합시다.
입력
입력의 첫 번째 줄에는 N과 M이 주어집니다(1≤N,M≤1000). 다음 N 줄에는 각각 세미나실의 상태를 나타내는 M길이의 문자열이 주어집니다.
출력
이 세미나가 끝날 때 교수들 사이에 형성할 수 있는 최대 우정 수를 출력합니다.
예제1
입력
4 5
.CGGC
.CGCG
CGCG.
.CC.C
출력
4
힌트
출처
USACO 2021 US Open Bronze