문제 1047 세종정보올림피아드(SJOI) 찾기(1)
[만든사람 : ]
문제 설명
크기가 n행 m열인 문자판이 주어진다. 문자판은 대문자 알파벳 S, J, O, I의 4문자로만 구성된다.
세종이는 원하는 칸에서 출발하여 위쪽, 아래쪽, 왼쪽, 오른쪽 중에서 한 방향으로 이동할 수 있다. 이동할 때마다 만나는 모든 문자를 연결하여 문자열을 만든다. 예를 들어 다음 그림과 같이 2행 4열로 이루어진 문자판이 주어졌을 때, 2행 1열에서 출발하여 오른쪽, 위쪽으로 이동하여 문자열을 만들면 “OIJ”를 만들어낼 수 있다.
경로 (2, 1) - (2, 2) - (1, 2)의 순으로 이동하여 "O" - "I" - "J"를 만든다.
세종이의 목적은 문자열 "SJOI"를 얻는 것이다. 주어진 문자판에서 얻을 수 있는 "SJOI"가 모두 몇 개인지 구하는 프로그램을 작성하시오.
입력 설명
첫 번째 줄에 n, m이 공백으로 구분되어 입력된다.
두 번째 줄부터 n줄에 걸쳐서 길이가 m인 문자열이 주어진다.
문자열의 각 문자는 "S", "J", "O", "I" 중 하나로 구성된다.
(1 <= n, m <= 15)
출력 설명
문자판에서 얻을 수 있는 "SJOI"의 최대 개수를 출력한다.
입력 예시 복사
2 4
SJOI
OIJO
출력 예시 복사
1
도움
위 예시에서는 (1, 1)-(1, 2)-(1, 3)-(1, 4)로 이동하여 하나의 “SJOI”를 얻을 수 있다.
출처/분류