경단 만들기

시간 제한2초메모리 제한256 MB

요약

N행 M열 격자에서 가로 또는 세로로 연속한 세 칸이 R, G, W 순서가 되도록 서로 겹치지 않는 막대를 최대한 많이 고른다.

문제

당신은 일본식 경단을 만드는 전문 제과사이다. 이제 경단을 꼬치에 꿰려고 한다.

경단은 $N$ 행 $M$ 열의 격자 칸에 놓여 있고, 각 칸에는 경단이 하나씩 있다. 경단의 색은 빨강(R), 초록(G), 하양(W) 중 하나이다.

격자에서 연속한 세 칸의 경단을 골라 꼬치 하나에 꿴다. 고르는 세 칸은 왼쪽에서 오른쪽으로 이어지거나 위에서 아래로 이어져야 한다.

만들려는 꼬치는 경단의 색이 순서대로 빨강, 초록, 하양인 꼬치이며, 이런 꼬치를 최대한 많이 만들고 싶다. 꼬치에 꿴 경단의 순서는 격자에서 고른 순서와 같아야 한다. 경단 하나를 두 개 이상의 꼬치에 꿸 수는 없다.

격자에 놓인 경단의 색이 주어질 때, 빨강, 초록, 하양 순서의 꼬치를 최대 몇 개 만들 수 있는지 구하는 프로그램을 작성하시오.

표준 입력으로 다음 데이터가 주어진다.

첫째 줄에 두 정수 $N$ 과 $M$ 이 공백으로 구분되어 주어진다.
다음 $N$ 개 줄 중 $i$ 번째 줄( $1 \le i \le N$ )에는 R, G, W로만 이루어진 길이 $M$ 의 문자열이 주어진다. 이 문자열의 $j$ 번째 문자( $1 \le j \le M$ )는 위에서 $i$ 번째 행, 왼쪽에서 $j$ 번째 열에 놓인 경단의 색이다.

표준 출력으로 한 줄을 출력한다. 만들 수 있는 꼬치의 최대 개수를 출력한다.