Without telpoters, this problemm can be solved by BFS, so we will consider applying BFS.

If you add edges betwee all the pairs of telpoters with the same character and do BFS, you will get TLE, because the number of edges can be at most \(\frac{(HW)^2}[2} \simeq 8 \times 10^{12}\).

Instead, we can do BFS in the following way:

• First of all, for each telepoter a, b, …, z, create a list of its positions
• During BFS, when reaching a square with a telepoter X for the first time, consider virtual edges to the other squares with telepoters X as well
• During BFS, if it reaches to a square with a telopter X but it’s not the first time, perform only normal BFS

Then, the problem can be solved in a total of \(O(HW)\) time.

Sample Code (C++): https://atcoder.jp/contests/abc184/submissions/18300509 Sample Code (Python): https://atcoder.jp/contests/abc184/submissions/18300509

Alternatively, we can add a hyper-vertex a, b, …, and z, add an edge of cost \(1\) from each square with telopter X to hyper-vertex X, add an edge of cost \(1\) from hyper-vertex X to each square with telepoter X, and perform 01BFS, so that we can also solve this problem in a total of \(O(HW)\) time.

Sample Code (C++): https://atcoder.jp/contests/abc184/submissions/18300674 Sample Code (Python): https://atcoder.jp/contests/abc184/submissions/18299832