Maze Tac Toe

题目描述

奶牛 Bessie 喜欢解迷宫。她也喜欢玩井字棋（更准确地说，是奶牛版井字棋，马上会描述）。农夫 John 找到了一种让她同时玩这两种游戏的新方法！

首先是奶牛井字棋：不同于在 $3 \times 3$ 的棋盘上放 X 和 O，奶牛们当然是在 $3 \times 3$ 的棋盘上放 M 和 O。在一个人的回合中，可以在任意空格中放置一个 'M' 或 'O'（这也是与标准井字棋的另一个区别：标准井字棋中一名玩家总是下 'X'，另一名玩家总是下 'O'）。奶牛井字棋的胜利条件是：第一个拼出 'MOO' 的玩家，无论是横向、纵向还是对角线。反着拼也算，例如在某一行拼出 'OOM' 也可以获胜。与标准井字棋一样，也可能到达一种没有任何获胜者的局面。奶牛井字棋的一步通常用 3 个字符表示：'Mij' 或 'Oij'，其中 $i$ 和 $j$ 都在 $1 \ldots 3$ 的范围内，分别表示要放置相应 'M' 或 'O' 的行与列。

为了挑战 Bessie，农夫 John 设计了一个由 $N \times N$ 个格子组成的正方形迷宫（$3 \leq N \leq 25$）。有些格子（包括所有边界格子）放着巨大的干草捆，阻止 Bessie 移动到这些格子上。Bessie 可以在迷宫中其他所有格子之间自由移动，每次可以向北、南、东、西四个方向走一步。有些格子里有一张纸，上面写着奶牛井字棋中的一步。当 Bessie 在迷宫中移动时，只要她踏入这样的格子，她就必须在自己同时进行的一盘奶牛井字棋中执行对应的一步（除非奶牛井字棋中对应的格子已经被占用，此时她不做任何操作）。这盘奶牛井字棋中她没有对手，但迷宫中的一些格子可能会与她最终拼出 'MOO' 的目标相对抗。

假设 Bessie 一旦获胜就立刻停止继续下奶牛井字棋，请你确定：通过在迷宫中适当地移动，她可能产生的不同获胜井字棋棋盘配置的数量。

输入格式

第一行输入为 $N$。

接下来 $N$ 行描述迷宫，每行包含 $3N$ 个字符。 每个格子由一个 3 字符的块描述，其内容可能是：'###' 表示墙，'...' 表示空地，'BBB' 表示 Bessie 所在的非墙格子，或一个奶牛井字棋的走子（表示一个会强制 Bessie 执行对应走子的非墙格子）。恰好有一个格子为 'BBB'。

输出格式

请输出一个整数：Bessie 通过在迷宫中移动、并在获胜后停止时，能够生成的不同获胜奶牛井字棋棋盘配置数量（可能为 0）。

7
#####################
###O11###...###M13###
###......O22......###
###...######M22######
###BBB###M31###M11###
###...O32...M33O31###
#####################

8

提示

在这个例子中，Bessie 最终可能到达 8 种获胜棋盘配置： O.M .O. MOM

O.. .O. .OM

O.M .O. .OM

O.. .O. MOM

O.. ... OOM

..M .O. OOM

... .O. OOM

... ... OOM

解释其中一种情况： O.. ... OOM 在这里，Bessie 可能先访问 O11 这个格子，然后移动到下方走廊，依次访问 O32、M33 和 O31。此时游戏停止，因为她已经获胜（例如，她将无法再访问位于她当前位置 O31 格子北边的 M11 格子）。

题目来源：Brian Dean

标签: USACO|2021|Silver

来源

USACO|2021|Silver