호그와트에서 수학하던 시절, 볼드모트 경은 아직 톰 마볼로 리들이라는 이름으로 불렸으며, 꽤나 매력적인 청년이었다. 그러나 수많은 어둠의 행위들이 그의 외모를 망가뜨렸고, 특히 코를 잃게 되었다.
의학은 계속 발전하고 있으며, 현대 성형외과의 기적이 이 문제를 해결해 줄 것이다. 그는 인공 코를 만드는 성형수술을 예약했고, 이제 그에게 남은 문제는 단 하나뿐이다 — 미래의 코가 위치할 자리를 선택해야 한다. 그는 이 문제에 수학적 관점에서 접근하기로 했다.
볼드모트 경의 얼굴은 \(n\)개의 행과 \(m\)개의 열로 이루어진 격자 직사각형으로 단순화하여 나타낼 수 있다. 볼드모트는 자신의 코가 정확히 두 개의 칸을 차지하며, 이 두 칸은 가로 또는 세로로 변을 공유해야 한다는 것을 알고 있다. 또한 일부 칸은 이미 그의 눈과 입으로 차지되어 있어서, 코가 그 자리를 차지할 수 없다는 것도 알고 있다. 이제 그는 자신의 얼굴에 새로운 코를 배치할 수 있는 방법의 수를 알고 싶어 한다. 볼드모트의 다음 어둠의 피해자가 되지 않으려면, 당신은 이 문제를 해결하는 것을 도와야 한다.
입력
입력 파일의 첫 번째 줄에는 두 정수 \(n\)과 \(m\) (\(1 \le n, m \le 1\,000\))이 주어진다 — 볼드모트 경의 얼굴 크기이다. 다음 \(n\)개의 줄에는 각각 \(m\)개의 문자가 주어진다 — 그의 얼굴에 대한 설명이다. 문자 '#'는 해당 칸이 이미 무언가로 차지되어 있음을 의미하고, 문자 '.'는 그 칸이 비어 있어 코가 차지할 두 칸 중 하나가 될 수 있음을 의미한다.
출력
출력 파일의 첫 번째 줄에 볼드모트의 얼굴에 코를 배치할 수 있는 방법의 수를 하나의 정수로 출력하라.
hanzch 9달 전 1
해리 포터와 볼드모트의 코
문제
호그와트에서 수학하던 시절, 볼드모트 경은 아직 톰 마볼로 리들이라는 이름으로 불렸으며, 꽤나 매력적인 청년이었다. 그러나 수많은 어둠의 행위들이 그의 외모를 망가뜨렸고, 특히 코를 잃게 되었다.
의학은 계속 발전하고 있으며, 현대 성형외과의 기적이 이 문제를 해결해 줄 것이다. 그는 인공 코를 만드는 성형수술을 예약했고, 이제 그에게 남은 문제는 단 하나뿐이다 — 미래의 코가 위치할 자리를 선택해야 한다. 그는 이 문제에 수학적 관점에서 접근하기로 했다.
볼드모트 경의 얼굴은 \(n\)개의 행과 \(m\)개의 열로 이루어진 격자 직사각형으로 단순화하여 나타낼 수 있다. 볼드모트는 자신의 코가 정확히 두 개의 칸을 차지하며, 이 두 칸은 가로 또는 세로로 변을 공유해야 한다는 것을 알고 있다. 또한 일부 칸은 이미 그의 눈과 입으로 차지되어 있어서, 코가 그 자리를 차지할 수 없다는 것도 알고 있다. 이제 그는 자신의 얼굴에 새로운 코를 배치할 수 있는 방법의 수를 알고 싶어 한다. 볼드모트의 다음 어둠의 피해자가 되지 않으려면, 당신은 이 문제를 해결하는 것을 도와야 한다.
입력
입력 파일의 첫 번째 줄에는 두 정수 \(n\)과 \(m\) (\(1 \le n, m \le 1\,000\))이 주어진다 — 볼드모트 경의 얼굴 크기이다. 다음 \(n\)개의 줄에는 각각 \(m\)개의 문자가 주어진다 — 그의 얼굴에 대한 설명이다. 문자 '
#'는 해당 칸이 이미 무언가로 차지되어 있음을 의미하고, 문자 '.'는 그 칸이 비어 있어 코가 차지할 두 칸 중 하나가 될 수 있음을 의미한다.출력
출력 파일의 첫 번째 줄에 볼드모트의 얼굴에 코를 배치할 수 있는 방법의 수를 하나의 정수로 출력하라.
예제 입력 1
예제 출력 1
예제 입력 2
예제 출력 2
예제 입력 3
예제 출력 3