hanzch   9달 전

해리 포터와 볼드모트의 코

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
2 초 1024 MB 78 67 42 100.000%

문제

호그와트에서 수학하던 시절, 볼드모트 경은 아직 톰 마볼로 리들이라는 이름으로 불렸으며, 꽤나 매력적인 청년이었다. 그러나 수많은 어둠의 행위들이 그의 외모를 망가뜨렸고, 특히 코를 잃게 되었다.

의학은 계속 발전하고 있으며, 현대 성형외과의 기적이 이 문제를 해결해 줄 것이다. 그는 인공 코를 만드는 성형수술을 예약했고, 이제 그에게 남은 문제는 단 하나뿐이다 — 미래의 코가 위치할 자리를 선택해야 한다. 그는 이 문제에 수학적 관점에서 접근하기로 했다.

볼드모트 경의 얼굴은 \(n\)개의 행과 \(m\)개의 열로 이루어진 격자 직사각형으로 단순화하여 나타낼 수 있다. 볼드모트는 자신의 코가 정확히 두 개의 칸을 차지하며, 이 두 칸은 가로 또는 세로로 변을 공유해야 한다는 것을 알고 있다. 또한 일부 칸은 이미 그의 눈과 입으로 차지되어 있어서, 코가 그 자리를 차지할 수 없다는 것도 알고 있다. 이제 그는 자신의 얼굴에 새로운 코를 배치할 수 있는 방법의 수를 알고 싶어 한다. 볼드모트의 다음 어둠의 피해자가 되지 않으려면, 당신은 이 문제를 해결하는 것을 도와야 한다.

입력

입력 파일의 첫 번째 줄에는 두 정수 \(n\)과 \(m\) (\(1 \le n, m \le 1\,000\))이 주어진다 — 볼드모트 경의 얼굴 크기이다. 다음 \(n\)개의 줄에는 각각 \(m\)개의 문자가 주어진다 — 그의 얼굴에 대한 설명이다. 문자 '#'는 해당 칸이 이미 무언가로 차지되어 있음을 의미하고, 문자 '.'는 그 칸이 비어 있어 코가 차지할 두 칸 중 하나가 될 수 있음을 의미한다.

출력

출력 파일의 첫 번째 줄에 볼드모트의 얼굴에 코를 배치할 수 있는 방법의 수를 하나의 정수로 출력하라.

예제 입력 1

2 3
...
...
복사

예제 출력 1

7
복사

예제 입력 2

3 4
..#.
#..#
..#.
복사

예제 출력 2

5
복사

예제 입력 3

5 8
........
.##..##.
........
#......#
.######.
복사

예제 출력 3

34
복사

댓글을 작성하려면 로그인해야 합니다.