此外,当小 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