AT_abc436_d [ABC436D] Teleport Maze

There is a maze consisting of a grid with $ H $ rows and $ W $ columns. Let $ (i,j) $ denote the cell at the $ i $ -th row from the top and $ j $ -th column from the left. The type of cell $ (i,j) $ is given as a character $ S_{i,j} $ , where each character has the following meaning: - `.` : Empty cell - `#` : Obstacle cell - Lowercase English letter (`a` - `z`): Warp cell In the maze, you can perform the following two types of actions any number of times in any order: - Walk: Move from the current cell to a cell that is one cell away in one of the four directions (up, down, left, right). However, you cannot move to an obstacle cell or outside the grid. - Warp: When you are at a warp cell, move to any warp cell with the same character written on it. Determine whether it is possible to move from cell $ (1,1) $ to cell $ (H,W) $ , and if possible, find the minimum total number of actions required.

The input is given from Standard Input in the following format: > $ H $ $ W $ $ S_{1,1}S_{1,2}\dots S_{1,W} $ $ \vdots $ $ S_{H,1}S_{H,2}\dots S_{H,W} $

If it is possible to move from cell $ (1,1) $ to cell $ (H,W) $ , print the minimum total number of actions required; otherwise, print `-1`.

### Sample Explanation 1 You can move from cell $ (1,1) $ to cell $ (3,4) $ by performing actions as follows: 1. Move from cell $ (1,1) $ to cell $ (1,2) $ by walking. 2. Move from cell $ (1,2) $ to cell $ (1,3) $ by walking. 3. Move from cell $ (1,3) $ to cell $ (3,2) $ by warping. 4. Move from cell $ (3,2) $ to cell $ (3,1) $ by walking. 5. Move from cell $ (3,1) $ to cell $ (3,4) $ by warping. The total number of actions is $ 5 $ , which is the minimum. ### Sample Explanation 2 It is impossible to move from cell $ (1,1) $ to cell $ (3,4) $ . ### Constraints - $ 1\leq H,W \leq 1000 $ - $ H\times W \geq 2 $ - $ H $ and $ W $ are integers. - $ S_{i,j} $ is `.`, `#`, or a lowercase English letter. - $ S_{1,1}\neq $ `#` - $ S_{H,W}\neq $ `#`