Description

小咪到夜市玩游戏，赢得了一副钥匙圈。这副钥匙圈上有个迷宫面板，里面有许多小钢珠：

将钥匙圈的面板向左或向右旋转 $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^*$。
  2. 若 $(i, j), (i+1, j), \ldots, (i^*-1, j)$ 间恰好有 $k$ 颗小钢珠，则原位置 $(i, j)$ 的小钢珠会掉到位置 $(i^*-k, j)$。
• 否则，该小钢珠将掉出迷宫。

给定迷宫与小钢珠的初始位置，请算出至少需要向左或向右旋转 $90$ 度几次，才能使每颗小钢珠都掉出迷宫。

以下是一个迷宫大小为 $10\times7$ 的例子：

Input Format

$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 代表该格为空且有小钢珠。
  2. s 代表该格为空且没有小钢珠。
  3. w 代表该格为迷宫挡板。

Output Format

如果存在使每颗小钢珠都掉出迷宫的旋转方式，请输出

$\textrm{ans}$

其中 $\textrm{ans}$ 为一个整数，代表所需的旋转次数。否则，输出

$-1$

10 7
w w w w w w w
w s s s s s w
w s s s s s w
w s w w w s w
w s s s w s w
w s b b w s w
w w w w w s w
s s s s s s w
s s s s s s w
w w w w w w w

7

5 3
s w s
s s s
w b w
w b w
s w s

5

5 3
s w s
w s w
s b s
w b w
s w s

-1

Hint

测试数据限制

• $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。
  2. $s_{i, j}, s_{i+1, j}, \ldots, s_{i^*-1, j}$ 均为 b。
• $n$ 与 $m$ 皆为整数。

评分说明

本题共有三组子任务，条件限制如下所示。 每一组可有一或多个测试数据，该组所有测试数据皆需答对才可获得该组分数。