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개이다.