P11906 [NHSPC 2023] E. 迷宫钥匙圈

小咪到夜市玩游戏，赢得了一副钥匙圈。这副钥匙圈上有个迷宫面板，里面有许多小钢珠：  将钥匙圈的面板向左或向右旋转 $90$ 度，可以使每颗仍在迷宫内的小钢珠向下掉落，直到该小钢珠掉出迷宫，碰到迷宫挡板，或碰到其他仍在迷宫内的小钢珠为止。更明确地说，这座迷宫可以用 $N\times M$ 的二维矩阵表示，一次的 $90$ 度旋转会将迷宫变换为 $M\times N$ 的二维矩阵，其中 * 一次 $90$ 度左旋转会将位置 $(i, j)$ 变换为位置 $(M-j+1, i)$。 * 一次 $90$ 度右旋转会将位置 $(i, j)$ 变换为位置 $(j, N-i+1)$。 此外，若旋转后位置 $(i, j)$ 有一颗小钢珠，则 * 若存在某个 $i' > i$ 满足 $(i', j)$ 为迷宫挡板，则 1. 设最小的 $i'$ 为 $i^*$。 1. 若 $(i, j), (i+1, j), \ldots, (i^*-1, j)$ 间恰好有 $k$ 颗小钢珠，则原位置 $(i, j)$ 的小钢珠会掉到位置 $(i^*-k, j)$。 * 否则，该小钢珠将掉出迷宫。 给定迷宫与小钢珠的初始位置，请算出至少需要向左或向右旋转 $90$ 度几次，才能使每颗小钢珠都掉出迷宫。 以下是一个迷宫大小为 $10\times7$ 的例子： 

> $n$ $m$ > $s_{1, 1}$ $s_{1, 2}$ $\ldots$ $s_{1, m}$ > $s_{2, 1}$ $s_{2, 2}$ $\ldots$ $s_{2, m}$ > $\vdots$ > $s_{n, 1}$ $s_{n, 2}$ $\ldots$ $s_{n, m}$ * $n$ 代表迷宫的行数。 * $m$ 代表迷宫的列数。 * $s_{i, j}$ 代表位置 $(i, j)$ 的状态，以字符 ``b``、``s``、``w`` 表示，其中 1. ``b`` 代表该格为空且有小钢珠。 1. ``s`` 代表该格为空且没有小钢珠。 1. ``w`` 代表该格为迷宫挡板。

如果存在使每颗小钢珠都掉出迷宫的旋转方式，请输出 > $\textrm{ans}$ 其中 $\textrm{ans}$ 为一个整数，代表所需的旋转次数。否则，输出 > $-1$

### 测试数据限制 * $1 \le n \le 15$。 * $1 \le m \le 15$。 * 对任意 $i \in \{1, 2, \ldots, n\}$ 与 $j \in \{1, 2, \ldots, m\}$，$s_{i, j}$ 只能是 ``b``、``s``、或 ``w``。 * 满足 $s_{i, j}$ 为 ``b`` 的 $(i, j)$ 对数介于 $1$ 与 $3$ 之间。 * 给定的迷宫保证不会有不稳定的状况，即若 $s_{i, j}$ 为 ``b``，则必定存在某个 $i^* > i$ 满足 1. $s_{i^*, j}$ 为 ``w``。 1. $s_{i, j}, s_{i+1, j}, \ldots, s_{i^*-1, j}$ 均为 ``b``。 * $n$ 与 $m$ 皆为整数。 ### 评分说明 本题共有三组子任务，条件限制如下所示。 每一组可有一或多个测试数据，该组所有测试数据皆需答对才可获得该组分数。 | 子任务 | 分数 | 额外输入限制 | | :------: | :----: | ------------ | | 1 | $37$ | 迷宫里的小钢珠数量为 $1$ | | 2 | $29$ | 迷宫里的小钢珠数量不超过 $2$ | | 3 | $34$ | 无额外限制 |