석고 모형 만들기

시간 제한4초메모리 제한1024 MB

요약

R행 C열 격자에 놓인 원기둥의 방향이 주어질 때, 원기둥을 모두 제거한 뒤 남는 석고 조각의 개수를 구합니다.

문제

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

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

틀은 $R \times C$ 개의 단위 정육면체로 나뉘고, 각 원기둥은 그중 하나에 꼭 맞게 들어가야 한다. 원기둥은 회전축이 가로를 향하거나, 세로를 향하거나, 바닥에 수직이 되도록 세 가지 방향으로 놓을 수 있다.

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

원기둥을 제거하고 남은 여섯 개의 석고 조각

원기둥 하나의 회전축을 세로로 향하게 바꾸면 같은 틀에서 5개의 조각이 만들어진다.

원기둥 하나의 회전축을 세로로 향하게 했을 때 남은 다섯 개의 석고 조각

현우가 원기둥을 배치한 방법이 주어질 때, 만들어지는 석고 조각의 개수를 구하여라.

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

다음 $R$ 개의 줄에는 현우가 원기둥을 배치한 방법이 주어진다. 각 줄은 길이 $C$ 의 문자열이며, 문자의 의미는 다음과 같다.

석고가 굳은 뒤 원기둥을 모두 제거했을 때 남는 석고 조각의 개수를 출력한다.