JOI 2018, 2018camp contest4 problemD- 꼬치 장인 > 문제은행 : 정보올림피아드&알고리즘




3162 : 꼬치 장인

제한시간
2000 ms   
메모리제한
256 MB   
해결횟수
6 회   
시도횟수
148 회   

문제

당신은 경단 코치를 만드는 장인이다

이제 꼬치막대에 경단을 끼우려고 한다.

경단은 NM열의 격자로 나누어진 칸에 배치되어있다

각 칸에는 경단이 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를 출력한다.




경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP