2894 : KOI깃발 (KOI Flag)
- 제한시간
- 1000 ms
- 메모리제한
- 128 MB
- 해결횟수
- 1 회
- 시도횟수
- 1 회
문제
한국 정보 올림피아드(KOI)에서는 올해 전국 대회를 홍보하기 위해 KOI 로고를 모티브로 한 깃발을 만들게했다.
깃발은 "좋은 깃발"이어야한다.
"좋은 깃발"은 알파벳 K, O, I 문자를 세로 M 행 옆 N 열의 직사각형 모양의 표에 배열 한 것으로,
K, O, I가 아래 그림과 같이 ( 즉 K의 오른쪽 옆에 O가 있고 K 아래에 I가 있는) 놓여있는 곳이 깃발에 적어도 1 개 이상 있는 것이다.
다음 그림은 "좋은 깃발"의 두 가지 예를 보이고 있다.
다음 그림은 "좋은 깃발"이 아닌 두 가지 예를 보이고 있다.
깃발의 가로 세로 크기와 깃발에 입력된 정보를 입력받아 “좋은 깃발”이 몇 가지가 만들어 질 수 있는지 구하는 프로그램을 작성하시오.
입력 예 1에 대해서는 아래 4가지 경우를 만들 수 있다.
입력형식
입력은 1 + M 행으로 구성된다. 첫 번째 줄에는 깃발의 크기를 나타내는 두 정수 M, N (2 <= M, N <= 20)가 공백으로 구분되어 적혀있다.
이 후 M행에는 N 개의 문자로 구성된 문자열이 적혀있다. 각 문자는 K, O, I, ? 중 하나이며, ? 이면 아직 정해지지 않았음을 나타낸다.
출력형식
입력 예2 3 ??O IIK |
출력 예4 |
입력 예2 2 ?? ?? |
출력 예3 |
입력 예3 3 ??I ??? O?K |
출력 예53 |
입력 예5 4 KOI? ???? ???? ???? ?KOI |
출력 예28218 |
Hint!