有一个 n×mn \times m n×m 的二维网格,ai,ja_{i, j}ai,j 表示网格的第 iii 行 第 jjj 列,其中 . 表示空地,# 表示墙。
.
#
你可以在任意一个空地放置一个射灯,它会沿着上下左右四个方向照亮碰到墙壁之前的所有空地。
很显然的,假设一共有 kkk 个空地,那么一共有 2k2^k2k 种放置射灯的方案,你需要统计每个方案中至少被一盏灯照到的空地个数,并求这个个数的总和。并将答案对 109+710^9+7109+7 取模。
使用您的 gxyz 通用账户