← 返回题目列表

AtCoder · code_festival_china_g

G. 弹药堆

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

问题

有一个 2尺寸维度网格 R \times C。一些牢房里有许多炸药仓库。

当仓库着火时,它最终会在未来的某个时间爆炸。 当仓库爆炸时,它会在 + 形状,火在所有四个侧面延伸。爆炸火势一直蔓延到其他仓库。爆炸火不会到达那些仓库后面的牢房。

遭受爆炸火灾的仓库可能会着火,也可能不会着火。 曾经经历过爆炸火灾但后来没有着火的仓库可能会遭受另一次爆炸火灾。那样的话,就和以前一样,仓库可能着火,也可能不着火。

爆炸的仓库不会再着火,但仍会阻挡爆炸火。

首先,你点燃了一个炸药仓库。 最后,所有的仓库都被炸毁了。

在那场灾难中,没有仓库同时爆炸。 (一些仓库可能同时着火。)

计算所有仓库爆炸的可能爆炸方式的数量。由于答案可能相当大,因此将其除以数字后将其打印为余数 1000000009(10^9+9).

爆炸方式是一组成对的仓库。每一对都是一个着火的仓库和一个因爆炸而起火的仓库。 当两种爆炸方式至少有一对不同的仓库时,它们是不同的。


输入

输入按以下格式给出。

R C
s_{(1,1)}s_{(1,2)} .. s_{(1,C)}
s_{(2,1)}s_{(2,2)} .. s_{(2,C)}
:
s_{(R,1)}s_{(R,2)} .. s_{(R,C)}
a b
  • 在第一行,您将得到两个整数 R,C (1 \leq R,C \leq 16) 分别由空格分隔,网格的行数和列数。
  • 正在关注 R 线是仓库的地方。 每行包含一个大小的字符串 C。每个字符串由 . 和 W.The i-th (1 \leq i \leq R) 行的 j-th (1 \leq j \leq C) 字符代表单元格 (i,j)。 如果角色是 .,单元格 (i,j) 是一个空单元格。 如果角色是 W,单元格上有一个仓库 (i,j).
  • 在下一行,您将得到两个整数 a,b (1 \leq a \leq R,1 \leq b \leq C) 以空格分隔。 (a,b) 是你第一次着火的仓库的地方。保证这个单元格上有一个仓库。
  • 保证至少有 1 仓库。

输出

输出一行,包含对所有仓库进行取模的爆炸方式数 1000000009。 确保在输出末尾插入换行符。


输入示例 1

3 4
W.W.
....
W.W.
1 1

输出示例 1

4

例如,有一种爆炸方式,如下所示。包括这种方式,还有 4 爆炸方式。

这样,位于 (1,3) 和 (3,1) 仓库起火 (1,1),仓库位于 (3,3) 仓库起火 (3,1)


输入示例 2

3 4
W.W.
.W.W
W.W.
2 2

输出示例 2

0

在这种情况下,并非所有仓库都会爆炸。


输入示例3

1 1
W
1 1

输出示例 3

1

输入示例 4

16 16
WWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWW
WWWWWWWWWWWWWWWW
1 1

输出示例 4

242986351

不要忘记输出数字除以后的余数 1,000,000,009.