3162 : 꼬치 장인
- 제한시간
- 2000 ms
- 메모리제한
- 256 MB
- 해결횟수
- 6 회
- 시도횟수
- 148 회
문제
당신은 경단 코치를 만드는 장인이다.
이제 꼬치막대에 경단을 끼우려고 한다.
경단은 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 점] 추가 제한은 없다.
출력형식
입력 예3 4 RGWR GRGG RGWW |
출력 예3 |
입력 예4 4 RGWR GRRG WGGW WWWR |
출력 예4 |
입력 예5 5 RGRGW GRRGW WGGWR RWRGW RGWGW |
출력 예6 |
Hint!
[1번 테스트케이스 설명]
다음과 같이 꼬치를 찌르면 경단이 순서대로 꽂힌 꼬치 3개를 만들 수 있다.
• 위에서 1번째 줄 왼쪽에서 1번째 경단에서 오른쪽으로 3개의 경단을 꼬치에 찌른다.
• 위에서 1번째 줄 왼쪽에서 4번째 경단에서 아래로 3개의 경단을 꼬치에 찌른다.
• 위에서 3번째 줄 왼쪽에서 1번째 경단에서 오른쪽으로 3개의 경단을 꼬치에 찌른다.
4개 이상의 꼬치를 만들 수 없기 때문에 3을 출력한다.
[2번 테스트케이스 설명]
다음과 같이 꼬치를 찌르면 경단이 순서대로 꽂힌 꼬치 4개를 만들 수 있다.
• 위에서 1번째 줄 왼쪽에서 1번째 경단에서 오른쪽으로 3개의 경단을 꼬치에 찌른다.
• 위에서 1번째 줄 왼쪽에서 4번째 경단에서 아래로 3개의 경단을 꼬치에 찌른다.
• 위에서 2번째 줄 왼쪽에서 2번째 경단에서 아래로 3개의 경단을 꼬치에 찌른다.
• 위에서 2번째 줄 왼쪽에서 3번째 경단에서 아래로 3개의 경단을 꼬치에 찌른다.
5 개 이상의 꼬치를 만들 수 없기 때문에 4를 출력한다.