You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

奶牛 Bessie 喜欢玩走迷宫。她同样喜欢玩井字棋（更准确地说，奶牛版的井字棋，马上会进行介绍）。Farmer 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 增加一些挑战，Farmer 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