北京地图
测试数据来自 wjszez/2099
【问题描述】
北京地图可以看作是 R*C 的网格,奥运会期间对有的地方要进行交通管制,有的地方不允许进入,有的地方对离开时的行驶方向有限制:有的只允许走到上下两个相邻的格子,有的只允许走到左右两个相邻的格子,没有的任何限制的地方上下左右四个方向都允许。
现在给你地图的描述,格子的描述如下:
● “+”表示可以向任意方向(上、下、左、右)移动一格;
● “-”表示只能向左右方向移动一格;
● “|”表示只能向上下方向移动一格;
● “*”表示该位置不能到达。
你的任务是计算出从左上角到右下角的最少需要经过的格子数。
【输入格式】
第一行一个整数t(1<=t=10),表示有t组测试数据。
每一个测试数据,第一行一个整数r,第二行一个整数 c,表示地图是 r 行 c 列的,接下来 r 行,每行 c 个字符,每个字符是{+,*,-,|}中的一种。
你可以假设左上角不会是“*”。
【输出格式】
输出有t行,每行一个整数表示对应测试数据所需的最少格子数,如果到达不了右下角输出-1。
【输入样例】
3
2
2
-|
+
3
5
+||+
+++|+
**--+
2
3
+*+
+*+
【输出样例】
3
7
-1
【数据范围】
对于100%的数据,1≤r,c≤20
信息
- ID
- 2507
- 难度
- (无)
- 分类
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 通过率
- ?
- 上传者