#P11808. [PA 2017] 摆砖 / Carcassonne
[PA 2017] 摆砖 / Carcassonne
题目背景
译自 Potyczki Algorytmiczne 2017 R5 Carcassonne [B] (CAR)。。
题目描述
给定一块 的棋盘,上面可能已经放了若干块 的砖。
现在要再放置 块 砖。如果放置的砖不是这个棋盘上的第一块砖,则要求放置的这块砖必须和之前棋盘上有的砖至少有一条公共边。
求方案数对 取模后的结果。
称两个方案是不同的,当且仅当存在一个格子,仅在一个方案中放了砖。
输入格式
第一行两个正整数 。
接下来 行,第 行一个长度为 的字符串 。
,代表 上放了砖;否则 ,代表没有放砖。
输出格式
输出一行一个整数,即方案数对 取模后的结果。
3 2
.#.
##.
#..
8
提示
- ;
- 。