2021.1.20.(목) ~ 1.21.(금) 에 SFPC가 열립니다. 자세한 사항은 11월에 학교로 안내될 공문을 참고해주세요.
문제1048--세종정보올림피아드(SJOI) 찾기(2)

1048: 세종정보올림피아드(SJOI) 찾기(2)

[만든사람 : ]
시간제한 : 1.000 sec  메모리제한 : 128 MB

제출
문제 설명



크기가 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를 얻음.

출처/분류