310022: CF1773D. Dominoes
Memory Limit：1024 MB
Time Limit：3 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
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
0Input
题意翻译
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$ 取最小值。Output
**题目大意：**
多拉喜欢玩多米诺骨牌。她在 $n \times m$ 的棋盘上标记一些方格，然后用 $2 \times 1$ 的多米诺骨牌填充其余的空方格。注意，多米诺骨牌不能放在被标记的方格上。
多拉的弟弟丹尼喜欢恶作剧，他会在多拉不在的时候在棋盘上再标记两个方格。请计算有多少种标记的方案，使得无法用多米诺骨牌填充所有空格。
如果方案数超过 $10^6$，请输出 $10^6$。
**输入格式：**
- 共 $n+1$ 行。
- 第一行，两个整数 $n$ 和 $m$ （$1 \leq n, m \leq 1000$）。
- 接下来 $n$ 行，每行 $m$ 个字符。字符“#”表示一个被标记的方格，字符“.”表示一个空方格。保证至少有两个空方格，并且可以用多米诺骨牌将所有空格填满。
**输出格式：**
- 一行，一个整数，为方案数与 $10^6$ 取最小值。
**输入输出样例：**
**输入样例 #1:**
```
3 6
...#..
......
#...##
```
**输出样例 #1:**
```
52
```
**输入样例 #2:**
```
2 2
..
..`
```
**输出样例 #2:**
```
2
```
**输入样例 #3:**
```
2 2
#.
#.
```
**输出样例 #3:**
```
0
```
注意：在 LaTeX 格式中，代码块应该用 `verbatim` 环境来表示，但是在这个文本框中无法直接展示 LaTeX 格式的代码块。**题目大意：** 多拉喜欢玩多米诺骨牌。她在 $n \times m$ 的棋盘上标记一些方格，然后用 $2 \times 1$ 的多米诺骨牌填充其余的空方格。注意，多米诺骨牌不能放在被标记的方格上。 多拉的弟弟丹尼喜欢恶作剧，他会在多拉不在的时候在棋盘上再标记两个方格。请计算有多少种标记的方案，使得无法用多米诺骨牌填充所有空格。 如果方案数超过 $10^6$，请输出 $10^6$。 **输入格式：** - 共 $n+1$ 行。 - 第一行，两个整数 $n$ 和 $m$ （$1 \leq n, m \leq 1000$）。 - 接下来 $n$ 行，每行 $m$ 个字符。字符“#”表示一个被标记的方格，字符“.”表示一个空方格。保证至少有两个空方格，并且可以用多米诺骨牌将所有空格填满。 **输出格式：** - 一行，一个整数，为方案数与 $10^6$ 取最小值。 **输入输出样例：** **输入样例 #1:** ``` 3 6 ...#.. ...... #...## ``` **输出样例 #1:** ``` 52 ``` **输入样例 #2:** ``` 2 2 .. ..` ``` **输出样例 #2:** ``` 2 ``` **输入样例 #3:** ``` 2 2 #. #. ``` **输出样例 #3:** ``` 0 ``` 注意：在 LaTeX 格式中，代码块应该用 `verbatim` 环境来表示，但是在这个文本框中无法直接展示 LaTeX 格式的代码块。
多拉喜欢玩多米诺骨牌。她在 $n \times m$ 的棋盘上标记一些方格，然后用 $2 \times 1$ 的多米诺骨牌填充其余的空方格。注意，多米诺骨牌不能放在被标记的方格上。
多拉的弟弟丹尼喜欢恶作剧，他会在多拉不在的时候在棋盘上再标记两个方格。请计算有多少种标记的方案，使得无法用多米诺骨牌填充所有空格。
如果方案数超过 $10^6$，请输出 $10^6$。
**输入格式：**
- 共 $n+1$ 行。
- 第一行，两个整数 $n$ 和 $m$ （$1 \leq n, m \leq 1000$）。
- 接下来 $n$ 行，每行 $m$ 个字符。字符“#”表示一个被标记的方格，字符“.”表示一个空方格。保证至少有两个空方格，并且可以用多米诺骨牌将所有空格填满。
**输出格式：**
- 一行，一个整数，为方案数与 $10^6$ 取最小值。
**输入输出样例：**
**输入样例 #1:**
```
3 6
...#..
......
#...##
```
**输出样例 #1:**
```
52
```
**输入样例 #2:**
```
2 2
..
..`
```
**输出样例 #2:**
```
2
```
**输入样例 #3:**
```
2 2
#.
#.
```
**输出样例 #3:**
```
0
```
注意：在 LaTeX 格式中，代码块应该用 `verbatim` 环境来表示，但是在这个文本框中无法直接展示 LaTeX 格式的代码块。**题目大意：** 多拉喜欢玩多米诺骨牌。她在 $n \times m$ 的棋盘上标记一些方格，然后用 $2 \times 1$ 的多米诺骨牌填充其余的空方格。注意，多米诺骨牌不能放在被标记的方格上。 多拉的弟弟丹尼喜欢恶作剧，他会在多拉不在的时候在棋盘上再标记两个方格。请计算有多少种标记的方案，使得无法用多米诺骨牌填充所有空格。 如果方案数超过 $10^6$，请输出 $10^6$。 **输入格式：** - 共 $n+1$ 行。 - 第一行，两个整数 $n$ 和 $m$ （$1 \leq n, m \leq 1000$）。 - 接下来 $n$ 行，每行 $m$ 个字符。字符“#”表示一个被标记的方格，字符“.”表示一个空方格。保证至少有两个空方格，并且可以用多米诺骨牌将所有空格填满。 **输出格式：** - 一行，一个整数，为方案数与 $10^6$ 取最小值。 **输入输出样例：** **输入样例 #1:** ``` 3 6 ...#.. ...... #...## ``` **输出样例 #1:** ``` 52 ``` **输入样例 #2:** ``` 2 2 .. ..` ``` **输出样例 #2:** ``` 2 ``` **输入样例 #3:** ``` 2 2 #. #. ``` **输出样例 #3:** ``` 0 ``` 注意：在 LaTeX 格式中，代码块应该用 `verbatim` 环境来表示，但是在这个文本框中无法直接展示 LaTeX 格式的代码块。