Project Summer 游戏
小 I 和小 B 最近沉迷一款叫做《Project Summer》 的游戏， 小 I 扮演这个游戏中需要逃生的无辜者（Innocent)， 小 B 扮演这个游戏中抓住无辜者， 阻止其逃生的背叛者（Betrayer）。
这个游戏的地图是一个 N 行 M 列 的矩形， 每个格点表示一个位置。
'#' 表示地图中的障碍物， '.' 表示地图中的空地， 此外， 地图中还有只有背叛者才能使用的传送门， 用小写字母 'a' - 'z' 标记， 它们在地图上成对出现。
角色可以花费 1 单位的时间从一个格子走到上下左右相邻的 4个空地中的另一个格子（不可以走出地图边界或者走到障碍物上）。此外， 当小 B 扮演的背叛者走到一个传送门上时， 他可以花费 1 单位的时间从当前格子传送到与当前格子相同字母的另一个传送门处（他也可以选择不传送， 此时没有花费任何时间， 待在原地不动）。
传送是双向的。 比如， 现在小 B 走到了标记为 'a' 的格子上， 那么他可以选择花费一单位的时间传送到另一个标记为 'a' 的格子上， 也可以选择不传送， 那么他就待在原地不动。
现在， 小 I 被小 B 的陷阱困住了， 无法移动。 给出地图上小 B 和小 I 所在的格子（他们都站在空地上）， 求小 B 最少需要花费多少时间才能走到小 I 所在的格子抓住他。 如果小 I 无法抓住小 B， 输出 -1
时间限制： 1000
内存限制： 65536
输入
第一行一个数字 T, 表示数据组数。 接下来描述 T 组数据， 每组数据最开始是两个正整数 N, M 表示地图是 N 行 M 列的矩形。 接下来 N 行， 每行 M 个字符， 表示地图。 在地图上， 用 '.' 表示空地，'#' 表示障碍物， 'a'-'z' 表示传送门， 'B' 表示小 B 的初始位置， 'I' 表示小 I 的初始位置。 对于每组数据， 保证在地图上标记相同的传送
门恰好出现两次。 T,N,M <= 100
输出
T 行， 第 i 行输出 'Case #i: t', 表示第 i 组数据的答案是 t. 小 B 最少需要 t 单位时间才能走到小 I 所在的格子。 如果小 I 无法抓住小B， 输出 -1
样例输入
3 5 5 Bx#.. #a.#. ..... ##..# .x.aI 5 5 BIa.a x#.x. .#.## ..... ##### 2 2 B# #I
样例输出
Case #1: 4 Case #2: 1 Case #3: -1
提示
对于第一组数据， 假设行从上到下标号 1 到 5， 列从左到右标号 1到 5， 小 B 初始在 (1, 1)。 小 B 的最优路线是： (1, 1) -> (1, 2) -> (2,2) -> (5, 4) -> (5, 5)。 也就是走到标记为 x 的传送门时忽略传送门， 走到标记为 a 的传送门时使用传送门。 对于第二组数据， 小 B 直接花费 1 单位时间向右走一格就可以抓住小 I, 故输出 1。 对于第三组数据， 小 B 无法走到小 I 所在的位置上， 故输出 -1。
相似题推荐
能量节点
题目描述
数轴上分布着 n 个能量节点，第 i 个节点的坐标为 xi 。
当两个节点的距离小于等于 d 时，会产生能量共鸣。
求一共有多少组节点会发生能量共鸣。
输入格式
第一行，两个整数表示 n 与 d。
第二行，n 个整数，表示 x1,x2,…,xn 。
输出格式
单个整数：表示有多少对点可以会产生能量共鸣。
输入样例
4 25 30 40 10 20
输出样例
5
说明提示
1≤n≤100,000，
1≤d≤1,000,000,000，
1≤xi≤1,000,000,000。
限制
时间限制：1000ms
内存限制：256MiB
已知数组`arr[6] = {2,4,6,8,10,12}`，前缀和数组`preSum[0]=0`，`preSum[i] = arr[0]+arr[1]+…+arr[i-1]`，则区间[2,4]（下标从0开始）的元素和为？（ ）
| A． 18 |
B． 24 |
| C． 30 |
D． 36 |
