JOI 2019 본선- JOI 찾기 > 문제은행 : 정보올림피아드&알고리즘




3374 : JOI 찾기

제한시간
2000 ms   
메모리제한
512 MB   
해결횟수
22 회   
시도횟수
83 회   

문제

J, O, I로만 이루어진 H행 W열의 행렬 A가 주어진다. 

이 때, 다음 조건을 만족시키는 (i, j, k, m) 쌍의 개수를 출력하여라.

 - 1 ≤ i < k ≤ H, 1 ≤ j < m ≤ W

 - A의 i번째 행 j번째 열은 J이다.

 - A의 i번째 행 m번째 열은 O이다.

 - A의 k번째 행 j번째 열은 I이다.


입력형식

첫째 줄에 행의 개수와 열의 개수를 뜻하는 H, W가 주어진다. (2 ≤ H, W ≤3,000) 그 후 H개의 줄에 길이 W인 문자열이 주어진다. i번째 줄 j번째 문자는 행렬의 i번째 행 j번째 열의 원소를 뜻한다.

출력형식

문제의 조건을 만족하는 (i, j, k, m)의 개수를 출력하여라.

입력 예

3 4
JOIJ
JIOO
IIII

출력 예

3

입력 예

4 4
JJOO
JJOO
IIJO
IIIJ

출력 예

17

Hint!

[입출력 예1 설명] 힌트. (i, j, k, m)로 가능한 쌍은 (1, 1, 3, 2), (2, 1, 3, 3), (2, 1, 3, 4)로 3개이다.



경기도 안양시 동안구 평촌대로 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