5.寻找宝石DsM100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
(gemstone.cpp) DsM100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【问题描述】DsM100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
lucky 婆婆制作宝石手环需要用到一种特殊的宝石。这一次，lucky 婆婆想要制作一种能力非常强大的魔法手环，她需要两种稀有的宝石——α 宝石和 β 宝石，这两种宝石只有在“迷失山洞”里才有，并且因为太过稀有，这两种宝石在“迷失山洞“也各自只有一颗，非常难找。劳拉和乔治听闻后，主动请缨，打算帮助 lucky 婆婆去“迷失山洞”里寻找这两种稀有的宝石。DsM100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
lucky 婆婆虽然不能亲自出来寻找宝石，但是她教给了劳拉和乔治一种咒语，念动咒语后，他们就能看清整个山洞，这样就不会迷路了。做好了完全的准备之后，劳拉和乔治前往了“迷失山洞”。DsM100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
“迷失山洞”是一个长为 n，宽为 m 的一个长方形山洞，山洞的入口就在长方形的左上角。为了尽快帮助 lucky 婆婆找到 α 宝石和 β 宝石，他们两人决定一起从洞口进入山洞后然后兵分两路分别寻找这两颗宝石，各自找到后，再原路返回到洞口集合。DsM100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
假设他们俩在山洞里，每过一个时刻可以向上下左右四个方向移动一步，那么请问，最少经过多少个时刻，他们俩才能在找到宝石后在洞口集合？DsM100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【输入格式】DsM100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
第一行输入两个正整数 n,m，分别表示山洞的长和宽。接下来 n 行，每行一个长为 m 的字符串，字符串中的字符的含义如下：DsM100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
字符‘.’表示山洞中可以行走的路径，数据保证山洞的左上角一定是‘.’；DsM100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
字符‘#’表示山洞的墙壁，也就是障碍物，无法行走；DsM100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
字符‘A’表示 α 宝石，数据保证只有一颗；DsM100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
字符‘B’表示 β 宝石，数据保证只有一颗；DsM100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【输出格式】DsM100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输出一行一个整数，表示答案。DsM100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【样例1输入】DsM100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
5 8DsM100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
......#BDsM100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
.###..#.DsM100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
.#A#..#.DsM100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
.#.#....DsM100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
......#.DsM100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【样例1输出】DsM100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
26DsM100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【样例1解释】DsM100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
找到 A 宝藏最少需要从洞口开始走 8 步，找到 B 最少需要走 13 步。因此，找到 A 并返回洞口需要 18 秒，找到 B 并返回需要 26 秒，集合最早在第 26 秒。因此输出 26。DsM100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【样例2输入】DsM100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
4 4DsM100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
....DsM100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
..B.DsM100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
....DsM100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
.A..DsM100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【样例2输出】DsM100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
8DsM100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【样例2解释】DsM100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
找到 A 宝藏最少需要从洞口开始走 4 步，找到 B 最少需要走 3 步。因此，找到 A 并返回洞口需要 8 秒，找到 B 并返回需要 6 秒，集合最早在第 8 秒。因此输出 8。DsM100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
DsM100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【数据范围】DsM100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
对于 40% 的测试数据，山洞里没有墙壁，也就是输入没有‘#’；DsM100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
对于另外 30% 的测试数据，n<=100；DsM100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
对于 100% 的测试数据，n<=1000。DsM100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
测试数据保证一定能从洞口出发找到两种宝石。DsM100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
