#P6038. 多拉的多米诺骨牌游戏

    ID: 6632 传统题 3000ms 1024MiB 尝试: 11 已通过: 5 难度: 7 上传者: 标签>CF2300提高+/省选-二分图建模阈值划分大小情况Kuhn 算法交替路深度优先搜索传递闭包

多拉的多米诺骨牌游戏

背景

多拉喜欢用多米诺骨牌玩游戏。她拿出一个n×mn \times m的桌面,将一些单元格标记为已占用,然后尝试用2×12 \times 1的多米诺骨牌填满所有未占用的单元格。

她的小弟弟丹尼喜欢捉弄他的姐姐。所以,当她离开时,他将两个未占用的单元格标记为已占用。他想要这样做,以至于不可能再用多米诺骨牌填满所有的未占用单元格。

帮助丹尼计算他可以选择这两个单元格的方式数量。由于丹尼只能数到一百万,如果该数量为xx,则输出min⁡(x,106)\min(x, 10^6)。

描述

输入

第一行包含两个整数nn和mm,表示桌面的尺寸(1≤n,m≤1000)(1 \leq n, m \leq 1000)。接下来的nn行每行包含mm个字符——桌面的初始状态。字符#表示一个已占用的单元格,字符.表示一个未占用的单元格。保证至少有两个未占用的单元格,并且有可能用多米诺骨牌填满所有未占用的单元格。

输出

令xx为丹尼将两个单元格标记为已占用,使得无法用多米诺骨牌填满所有未占用单元格的方式数量。

输出一个整数min⁡(x,106)\min(x, 10^6)。

示例

3 6
...#..
......
#...##
52
2 2
..
..
2
2 2
#.
#.
0