传送门

题目描述

有一个 n×m 的网格，起点为 (1,1)，终点为 (n,m)。网格中有一些传送门，传送门成对出现，进入一个传送门会立即传送到配对的传送门。求从起点到终点的最短路径长度。

输入格式

第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 1000)，表示网格的行数和列数。 接下来的 n 行每行包含 m 个字符，表示网格的布局。字符 '.' 表示空地，字符 '#' 表示障碍物，字符 'a'-'z' 表示传送门（同一字母的传送门成对出现）。

保证起点 (1,1) 和终点 (n,m) 都是空地。

输出格式

输出一个整数，表示从起点到终点的最短路径长度。如果无法到达终点，输出 -1。

样例 1

3 3
.a.
..#
#a.

2

提示

一开始在起点 (1,1)，步骤为 0。 移动到 (1,2)，步骤为 1，进入传送门 'a'，传送到 (3,2)，步骤仍为 1。 移动到 (3,3)，步骤为 2，达到终点。