Dominoes

题意翻译

Dora喜欢玩多米诺骨牌。玩法是在一个 $n×m$ 的表格中标记一些格子，然后用 $2×1$ 的多米诺骨牌填满其他空格子。注意，多米诺骨牌不能放在标记过的格子上。 Dora的弟弟Dani喜欢搞恶作剧，趁Dora不在时，他会在表格中又标记两个格子。请告诉他有多少种标记的方案，使多米诺骨牌无法填充到所有空格子里。 但是Dani只能数到 $10^6$。如果方案数超过 $10^6$，请输出 $10^6$。 ### 输入格式 一共 $n+1$ 行。 第一行，两个整数 $n$ 和 $m$ ( $1≤n,m ≤1000$ )。 下面 $n$ 行，每行 $m$ 个字符。字符“#”表示一个被标记的格子，字符“.”表示一个空格子。保证至少有两个空格子，并且可以用多米诺骨牌将所有空格子填满。 ### 输出格式 一行，一个整数，为方案数与 $10^6$ 取最小值。

题目描述

Dora likes to play with dominoes. She takes $ n \times m $ table, marks some cells as occupied, and then tries to fill all unoccupied cells with $ 2 \times 1 $ dominoes. Her little brother Dani loves to play pranks on his older sister. So when she is away, he marks two more unoccupied cells as occupied. He wants to do it in such a way that it will be impossible to fill all unoccupied cells with dominoes. Help Dani to count the number of ways he can select these two cells. Since Dani can only count to one million, if this number of ways is $ x $ , output $ \min(x, 10^6) $ .

输入输出格式

输入格式

The first line contains integers $ n $ and $ m $ ( $ 1\le n, m\le 1000 $ ). Next $ n $ lines contain $ m $ characters each — the initial state of the table. Character "\#" corresponds to an occupied cell, and character "." corresponds to an unoccupied cell. It is guaranteed that there are at least two unoccupied cells, and that it is possible to fill all unoccupied cells with dominoes.

输出格式

Let $ x $ be the number of ways Dani can mark two cells in such a way that it will be impossible to fill all unoccupied cells with dominoes. Print one integer $ \min(x, 10^6) $ .

输入输出样例

输入样例 #1

3 6
...#..
......
#...##

输出样例 #1

52

输入样例 #2

2 2
..
..

输出样例 #2

2

输入样例 #3

2 2
#.
#.

输出样例 #3

0