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