#P1381. Guards In The Storehouse
Guards In The Storehouse
题目描述
给定一个 的网格,有些位置是障碍(x
),有些位置是空地(.
)。
可以在每一个空地处放一个摄像头,这个摄像头会向右,向下监视第一个障碍前的所有方格。现在你需要在空地上安排摄像头,使得最多 个空地没有被摄像头监视。输出方案数对 取模。
输入格式
第一行两个整数 ,,。
接下来 行,每行 个字符。
输出格式
一个整数表示答案,对 取模。
1 3
.x.
3
2 2
xx
xx
1
2 2
..
..
10
3 1
x
.
x
2