テレポーターがなければこの問題は 幅優先探索 で解くことができるので、幅優先探索をすることを考えます。

同じ文字のテレポーター間全てに辺を張って幅優先探索をすると、辺の数が最大で \(\dfrac{(HW)^2}{2} \simeq 8 \times 10^{12}\) 本程度になるため、 TLE してしまいます。

そこで、以下のように幅優先探索を行います。

• テレポーター a, b, …, z がある場所のリストをあらかじめ作っておく
• 幅優先探索で、初めてテレポーター X のある場所に来た場合、他のテレポーター X への辺が張られているとして幅優先探索を行う
• 幅優先探索で、テレポーター X のある場所に来たが初めてではない場合、通常の幅優先探索を行う

これで、 \(O(HW)\) でこの問題を解くことができます。

回答例 (C++) : https://atcoder.jp/contests/abc184/submissions/18300509
回答例 (Python) : https://atcoder.jp/contests/abc184/submissions/18299994

また、超頂点 a, b, …, z を用意し、テレポーター X のある場所から超頂点 X にコスト 1 の辺を張り、超頂点 X からテレポーター X のある場所にコスト 0 の辺を張り、01BFS をすることでも、 \(O(HW)\) で解くことができます。

回答例 (C++) : https://atcoder.jp/contests/abc184/submissions/18300674
回答例 (Python) : https://atcoder.jp/contests/abc184/submissions/18299832