32031번 - 석고 모형 만들기

현우는 틀에 석고를 붓고 굳혀서 다양한 모양을 만들어 보는 취미가 있다. 현우가 이번에 준비한 틀은 세로 길이가 R, 가로 길이가 C, 높이가 1인 직육면체 모양이다.

만들어진 모양이 단순하면 석고 모형을 만드는 재미가 떨어진다. 그래서 현우는 지름과 높이가 1인 원기둥을 R × C개 가져왔다. 현우는 원기둥을 모두 틀 안에 배치한 다음 빈 공간에 석고를 붓기로 했다.

원기둥을 틀에 배치할 때에는, 틀을 R × C개의 단위 정육면체로 나눈 뒤 각 단위 정육면체 안에 꼭 맞게 넣어야 한다. 원기둥을 배치할 수 있는 방향은 세 가지가 있는데, 회전축이 가로를 향하거나, 세로를 향하거나, 바닥에 수직이도록 놓을 수 있다.

현우가 원기둥을 모두 배치하고 나면 틀에 석고를 부어 굳힌 뒤 모든 원기둥을 제거할 것이다. 그러면 여러 개의 분리된 석고 조각이 만들어진다. 예를 들어, 세로 길이가 1이고 가로 길이가 2인 직육면체 틀에 두 원기둥을 회전축이 바닥에 수직이도록 배치한다면 총 6개의 석고 조각이 만들어진다.

한편, 위 예시에서 원기둥 하나의 회전축이 세로를 향하도록 배치를 바꾼다면 총 5개의 석고 조각이 만들어진다.

현우가 틀에 원기둥을 배치하는 방법이 주어졌을 때, 총 몇 개의 석고 조각이 만들어질지 구해 보자.

첫째 줄에 틀의 세로 길이와 가로 길이를 나타내는 정수 R와 C가 공백을 사이에 두고 주어진다. (1 ≤ R, C ≤ 200)

다음 R개의 줄에 걸쳐 현우가 틀에 원기둥을 배치하는 방법이 주어진다. 각 줄에는 길이 C의 문자열이 주어지며, 문자열을 구성하는 문자의 의미는 아래와 같다.

• H: 회전축이 가로를 향하는 원기둥
• I: 회전축이 세로를 향하는 원기둥
• O: 회전축이 바닥에 수직인 원기둥

첫 줄에 석고를 굳힌 뒤 원기둥을 모두 제거하면 만들어지는 석고 조각의 개수를 출력한다.