3874: 交通管制(traffic)

traffic.in/traffic.out
国庆期间常州需要对部分地方进行交通管制，常州地图可以看作是 R*C 的网格，有些 地方不能进，有些地方离开时对行驶方向作出限制：有些地方只允许走到上下两个相邻的格 子；有些地方只允许走到左右两个相邻的格子；有些地方任何限制的地方上下左右四个方向 都允许。 现在给你常州国庆期间管制地图地图的描述，格子的描述如下： 
1. “+”表示可以向任意方向（上、下、左、右）移动一格； 
2. “-”表示只能向左右方向移动一格； 
3. “|”表示只能向上下方向移动一格；
4. “*”表示该位置不能到达。 
你的任务是需要根据管制地图计算出从常州左上角到常州右下角的最少需要经过多少格 子？

第一行一个整数 T(1<=T=10)，表示有 T 组测试数据。 每一个测试数据，第一行一个整数 R，第二行一个整数 C，表示 R 行 C 列的，接下来 R 行，每行 C 个字符，每个字符是{*,|,+,-}中的一种。左上角不会是“*”。

输出有 T 行，每行一个整数表示对应测试数据所需的最少格子数，如果到达不了右下角 输出-1。

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

3
7
-1