Description

为了赚点钱，你决定参与一个科学实验。你会被喂很多披萨，然后再吃更多的披萨，接着你需要骑着一辆仅靠披萨驱动的滑板车穿越城市。当然，城市里有很多交叉路口，这些路口受到严格控制。有些路口是禁止进入的；有些只允许你在离开路口时向北或向南移动；有些只允许你在离开路口时向东或向西移动；剩下的则允许你朝任意方向（北、南、东或西）移动。

幸运的是，你的科学朋友给了你一张城市地图（在一个披萨盒的背面），上面用一些符号表示你可以如何在城市中移动。具体来说，盒子上有 4 种不同的符号：

• 符号 + 表示我们可以从这个位置向任意方向（北/南/东/西）移动。
• 符号 - 表示我们只能从这个位置向东或向西移动。
• 符号 | 表示我们只能从这个位置向北或向南移动。
• 符号 * 表示我们不能占据这个位置。

你的任务是确定从城市的西北角移动到东南角需要经过多少个交叉路口。

Input Format

输入以一个数字 $t (1 \leq t \leq 10)$ 开始，单独占一行，表示文件中包含多少个不同的测试用例。每个测试用例以一个数字 $r$ 开始，接下来一行是一个数字 $c$，其中 $(1 \leq r, c \leq 20)$。接下来的 $r$ 行包含 $c$ 个字符，其中每个字符是 {+, *, -, |} 中的一个。你可以假设城市的西北角可以被占据（即，它不会被标记为 *）。

Output Format

输出将有 $t$ 行，每行一个整数。第 $i (1 \leq i \leq t)$ 行的整数表示从城市的西北角移动到东南角所需经过的最少交叉路口数。如果无法从西北角到达东南角，则对该测试用例输出 $-1$。

3
2
2
-|
*+
3
5
+||*+
+++|+
**--+
2
3
+*+
+*+

3
7
-1

Hint

题面翻译由 ChatGPT-4o 提供。