← 返回题目列表

AtCoder · typical90_w

023. 避免战争(★7)

中文机器翻译题面 查看原题

配点: 7 点

問題文

縦 H 方形,水平 W 有一个由正方形组成的网格,从上往下 i 行/从左起 j 选择列中的方块。 当表示为 (i,j) 代表。 每个方格都涂上一种颜色, (i,j) 的颜色是 C_{i,j} 是 在 # 当黑色时,C_{i,j} 是 在 . 时为白色。

您选择一些白色方块(1 您也不必选择),王 放置块。 王 放置防止它们互相攻击(稍后描述)的放置数量为10^9+7 求除以后的余数。

但是,有 2 两者的放置方式不同。 “有一些白色方块,其中一个上面放置了一个国王,而另一个上面没有放置白色方块。” 我告诉你一件事。

“诸王不相攻”是什么意思? 国王的放置位置有任何不同 2 质量 从 (i,j) 和 (k,l) 中, 输出 |i-k|>1 或 至少 |j-l|>1 成立。

制約

  • 1 \leq H,W \leq 24
  • H,W 是一个整数
  • C_{i,j} 是 您也可以写 # 或 至少 .
  • 至少 1 有 2 个白色方块

小課題

  1. (1 点) 1 \leq H,W \leq 4
  2. (1 点) 1 \leq H,W \leq 9
  3. (2 点) 1 \leq H,W \leq 17
  4. (3 点)没有额外的限制。

入力

输入是按以下格式从标准输入给出的。

H W
C_{1,1}\cdots C_{1,W}
\vdots
C_{H,1}\cdots C_{H,W}

出力

满足条件的放置数量为 请打印除以10^9+7 后的余数。


入力例 1

1 3
...

出力例 1

5

下面 5 有一条街。 ( o 代表放置国王的方格。 )

...     o..     .o.     ..o     o.o

这是一个小任务 满足 1,2,3,4 约束。


入力例 2

3 3
.#.
#..
.##

出力例 2

13

下面 13 有一条街。 ( o 代表放置国王的方格。 )

.#.     o#.     .#o     .#.     .#.     .#.     o#o
#..     #..     #..     #o.     #.o     #..     #..
.##     .##     .##     .##     .##     o##     .##

o#.     o#.     .#o     .#.     o#o     o#.
#.o     #..     #..     #.o     #..     #.o
.##     o##     o##     o##     o##     o##

这是一个小任务 满足 1,2,3,4 约束。


入力例 3

8 9
######.##
####..##.
..#...#..
###...###
#....##.#
.##......
#.####..#
#.#######

出力例 3

273768

这是一个小任务 满足 2,3,4 约束。


入力例 4

17 17
.####...#.....#.#
.#....#.#####...#
#...##.##...#..##
..#..####..#...##
.#..#..#.#.##...#
.#.#.#...#.##..#.
#...#..#..##..###
###.#..###..###..
...#.##.##.#....#
..####....#.#...#
.##...##.#.#...#.
..########...###.
#..##....#.......
##.##..###.#.##..
.##....#........#
....#####..##.#..
.###...##..##.#..

出力例 4

314465173

10^9+7 后的余数。

这是一个小任务 满足 3,4 约束。


入力例 5

22 18
.##.##.#.#.#...##.
####.#..###.#.#..#
#####.##...##.###.
...#.#.#.##.##.###
..#.##.#.#....#...
#.###.##....###..#
....#####...#...#.
.#..##..#..###....
....#..##.#.#..#.#
###.#.....#..##.#.
#..#..#.#.##..###.
#...#....##..###..
..#...#..###..##..
.#....#.#.#..###.#
##.#.#..#..###..##
....###.##.##.##..
#...####.#.#..##..
..#.###.###.###.##
#...##.#.#.#...#.#
#..###..########..
#.##.#####.#..#.##
#..#........#...#.

出力例 5

47296634

这是一个小任务 满足 4 约束。