s02182. 传送门 未做

一个 $n\times m$ 的地图，. 是空地、# 是障碍、S 是起点、T 是终点。地图上还有若干成对的传送门（同一对用同一个小写字母标记，$a\sim d$；保证每个字母要么不出现、要么恰好出现两次）：走进一个传送门格会立即被送到配对的另一格（不消耗额外步数）。每次移动花费 1 步（上下左右走一格或走进传送门）。求从 $S$ 到 $T$ 的最少步数；无法到达输出 $-1$。

第一行两个整数 $n,m$。接下来 $n$ 行，每行 $m$ 个字符（.、#、S、T、a~d）。

一行一个整数，最少步数；无法到达输出 -1。

• 对于 30% 的数据：$n,m\le 10$
• 对于 60% 的数据：$n,m\le 100$
• 对于 100% 的数据：$n,m\le 1000$，传送门对不超过 4 对