커질 수 있는 아름다운 삼각형

N×M 격자의 점 중 세 색이 모두 다른 삼각형 가운데, 두 꼭짓점을 공유하면서 넓이가 더 큰 다른 삼각형이 존재하는 것의 개수를 센다.

보통5완전 탐색기하조합론수학아직 제출이 없습니다시간 제한2초메모리 제한128 MB

문제

N×M 크기의 직사각형이 1×1 단위 정사각형으로 나뉘어 있다. 각 단위 정사각형의 중심에는 점이 하나 있으며, 색은 R(빨강), G(초록), B(파랑) 중 하나이다.

서로 다른 세 점을 골라 서로 연결한다. 세 점이 한 직선 위에 있어도 하나의 삼각형으로 보며, 이때 넓이는 0이다. 세 꼭짓점의 색이 모두 다르면 그 삼각형을 아름다운 삼각형이라고 한다.

아름다운 삼각형 A와 B가 두 꼭짓점을 공유하고, B의 넓이가 A보다 크다면 A는 커질 수 있는 아름다운 삼각형이다.

직사각형의 색 배치가 주어졌을 때, 서로 다른 커질 수 있는 아름다운 삼각형의 개수를 구하라.

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ N, M ≤ 50)

둘째 줄부터 N개의 줄에 직사각형의 색 배치가 주어진다. 각 문자는 R, G, B 중 하나이다.

출력

커질 수 있는 아름다운 삼각형의 개수를 출력한다.