도미노

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

요약

빈 칸 두 개를 막았을 때 도미노로 전부 채울 수 없게 되는 경우의 수를 세고, 최대 1000000으로 제한하여 출력합니다.

난이도: 어려움10점 중 8점
유형: 그래프, DFS, 위상 정렬
정답자: 아직 제출이 없습니다

문제

도라는 도미노 놀이를 좋아한다. 도라는 $n \times m$ 표를 준비하고 일부 칸을 점유된 칸으로 표시한 뒤, 점유되지 않은 모든 칸을 $2 \times 1$ 도미노로 채우려고 한다.

도라의 남동생 다니는 누나를 자주 골탕 먹인다. 도라가 자리를 비운 사이, 다니는 점유되지 않은 칸 두 개를 더 점유된 칸으로 바꾼다. 이때 점유되지 않은 모든 칸을 도미노로 채울 수 없게 되도록 두 칸을 고르려고 한다.

다니가 이 두 칸을 고르는 방법의 수를 구하라. 다니는 백만까지만 셀 수 있으므로, 방법의 수를 $x$ 라 하면 $\min(x, 10^6)$ 을 출력한다.

입력

첫 줄에 정수 $n$ 과 $m$ 이 주어진다 ( $1\le n, m\le 1000$ ). 이어서 $n$ 개의 줄에 각각 $m$ 개의 문자가 주어지며, 이는 표의 초기 상태이다. 문자 \#는 점유된 칸, 문자 .는 점유되지 않은 칸을 뜻한다. 점유되지 않은 칸은 적어도 두 개 있으며, 도미노로 점유되지 않은 모든 칸을 채울 수 있다고 보장된다.

출력

다니가 두 칸을 점유된 칸으로 표시해서 점유되지 않은 모든 칸을 도미노로 채울 수 없게 만드는 방법의 수를 $x$ 라 하자. 정수 $\min(x, 10^6)$ 을 하나 출력한다.

예제3

예제 1
입력
```
3 6
...#..
......
#...##
```
예상 출력
```
52
```
예제 2
입력
```
2 2
..
..
```
예상 출력
```
2
```
예제 3
입력
```
2 2
#.
#.
```
예상 출력
```
0
```