문제
당신은 경단 꼬치를 만드는 장인이다.
이제 꼬치막대에 경단을 끼우려고 한다.
경단은 N행 M열의 격자로 나누어진 칸에 배치되어있다.
각 칸에는 경단이 1개씩 들어있다.
각각의 경단은 빨강 (R), 녹색 (G), 흰색 (W) 중 하나의 색으로 칠해져있다.
당신은 왼쪽에서 오른쪽 방향 또는 위에서 아래 방향으로, 연속한 3개를 꼬치막대에 끼울 수 있다.
단, 꼬치에 끼워지는 경단의 순서는 바꿀 수 없다.
지금 당신은 빨강, 녹색, 흰색 경단이 1개씩 순서대로 박힌 꼬치를 가능한 한 많이 만들고 싶다.
한 경단을 2개 이상의 꼬치로 찌를 수 없으며, 꼬치에 꽂힌 경단의 순서를 바꿀 수 없다는 점에 유의하자.
당신은 꼬치를 최대 몇 개나 만들 수 있을까?
입력
첫 번째 줄에 격자의 크기를 나타내는 자연수 N과 M이 주어진다.
두 번째 줄부터 N개의 줄에 격자의 정보를 나타내는 M개의 글자가 주어진다.
각 글자는 R, G, W 중 하나이며, 각각 빨강, 녹색, 흰색을 나타낸다.
[제한]
모든 입력 데이터는 다음을 만족한다. 1 ≦ N ≦ 3,000 1 ≦ M ≦ 3,000
부분문제 1 [13 점] • N ≦ 4 • M ≦ 4
부분문제 2 [20 점] • N ≦ 10 • M ≦ 10
부분문제 3 [67 점] 추가 제한은 없다.
출력
경단이 빨강, 녹색, 횐색 순서로 꽂힌 꼬치 개수의 최댓값을 한 줄에 출력하라.
예제1
입력
34
RGWR
GRGG
RGWW
출력
3
예제2
입력
44
RGWR
GRRG
WGGW
WWWR
출력
4
예제3
입력
55
RGRGW
GRRGW
WGGWR
RWRGW
RGWGW
출력
6
힌트
태그
출처
JOI 2018