Informatica Online Judge

  꼬치구이 장인 #1 [2198 / 0896]

Time Limit(Test case) : 2000 (ms)
Number of users who solved : 7   Total Tried : 5


The Champion of this Problem (C++) : gs18070 - 0ms / 547byte
My Best Submission (C++) : N/A

[JOI 2018 honsen]

Background

경곽이는 꼬치구이를 만드는 장인이다.

지금 경곽이는 각 재료를 꼬치에 끼우고 있다.

각 재료는 N행, M열 로 구분된 격자칸에 배치되어 있다.

각 칸에 재료가 1개씩 배치되어 있다.

각각의 재료에는 빨강(R) 초록(G), 흰색(W) 중 하나의 색깔로 되어있다.

경곽이는 왼쪽으로부터 오른쪽 방향, 또는 위로부터 아래쪽 방향으로 연속된 3칸으로부터 재료를 가져와서 꼬치에 끼워 꼬치구이를 만든다.

즉, 꼬치구이 하나에 들어가는 재료는 정확하게 3개이다.

지금 경곽이는 빨강, 초록, 흰색의 재료가 하나씩 순서대로 구성된 꼬치구이를 최대한 많이 만들고자 한다.

꼬치구이에 끼우는 재료의 순서는 원래 격자판에서 가져온 순서대로 만들어야 한다.

또 같은 재료를 2개의 꼬치구이에 사용할 수 없다.

경곽이가 만들 수 있는 최대 꼬치구이의 수를 구하시오.

Input

첫 번째 줄에는 N, M이 공백으로 구분되어 입력된다.

다음 줄부터 N줄에 걸쳐서 길이가 M인 문자열이 주어진다. 문자열을 이루는 문자는 R, G, W중 하나이다.

[입력값의 정의역]
#1 : $1 <= N, M <= 10 $

Output

만들 수 있는 최대 꼬치구이의 수를 출력한다.

IO Example

입력
3 4
RGWR
GRGG
RGWW

출력
3

* (1,1)부터 (1,3)까지 하나의 꼬치구이를 만들 수 있다.
(1,4)부터 (3, 4)까지 하나의 꼬치구이를 만들 수 있다.
(3,1)부터 (3,3)까지 하나의 꼬치구이를 만들 수 있다.
이 보다 더 많이 만들 수 없으므로 3개

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]