P15996 [ICPC 2020 NAC] Mini Battleship

*战舰* 是一款双人游戏。每位玩家拥有自己的棋盘，棋盘对对手不可见。每位玩家在棋盘上秘密放置若干艘船。每艘船占据水平或垂直方向上一段连续的一个或多个格子。船之间不能重叠。所有船只被视为不同的，即使它们尺寸相同。 放置完船只后，玩家轮流通过报出对手棋盘上的坐标来向对手的船只开火。对手必须如实告知该次射击是命中还是未命中。当一艘船的所有格子都被击中时，该船沉没（“你击沉了我的战舰！！！”）。当一名玩家的所有船只都被击沉时，该玩家失败。 鲍勃正在与爱丽丝玩一局迷你战舰游戏。常规战舰在 $10 \times 10$ 的棋盘上进行，共有 $5$ 艘船。迷你战舰的规模要小得多，棋盘大小不超过 $5 \times 5$，船只数量也可能少于 $5$ 艘。 鲍勃想知道，根据他目前已知的信息，爱丽丝的棋盘上可能有多少种船只的放置方案。如果爱丽丝在作弊（或者游戏设置不可能成立），答案将为 $0$。

输入的第一行包含两个空格分隔的整数 $n$（$1 \le n \le 5$）和 $k$（$1 \le k \le 5$），表示游戏在 $n \times n$ 的棋盘上进行，共有 $k$ 艘船。 接下来的 $n$ 行，每行包含一个字符串 $s$（$|s| = n$）。这是鲍勃目前看到的爱丽丝棋盘的情况： - 字符 ‘X’ 表示鲍勃的一次射击未命中。 - 字符 ‘O’（大写字母 O，不是数字零）表示鲍勃的一次射击命中。 - 点号 ‘.’ 表示鲍勃尚未射击的格子。 接下来的 $k$ 行，每行包含一个整数 $x$（$1 \le x \le n$）。这些是船只的尺寸。

输出一个整数，表示 $k$ 艘不同的船能够放置在爱丽丝的棋盘上并与鲍勃所见情况一致的方式总数。

翻译由 DeepSeek V3.2 完成