레이팅 미적용Queen Sofia is trapped on a mysterious chessboard of \(n\) rows and \(m\) columns. The
board contains her starting square (labeled "S") and her exit square (labeled "E").
Unfortunately, the path to the exit is not easy - some squares are blocked (labeled
"#"), while others are free (labeled ".").
But the board also hides magical portals! Some of the numbers between 1 and 9
appear exactly twice on the board. If the queen lands on a square with a number,
she can teleport to another square on the board with the same number without
spending extra moves to move through the portal. The queen cannot continue moving in the same
direction after passing through the portal without an additional cost of 1 move.
The queen can move in a chess-like manner - in one move she can jump to any square that is on the same
diagonal, row, or column as her, but only if there are no blocked squares between her and that
square (including the starting and ending squares of the move).
Find and print the smallest number of moves required for the queen to reach the exit square from the
starting square, or print -1 if this is not possible.
The first line contains the integers \(n\) and \(m\) (\(1 \le n\), \(m \le 1000\)), the number of rows and the number of
columns of the board.
Each of the next \(n\) lines contains \(m\) characters \(c_{ij}\), the description of the board. Each character of the
board will be one of S, E, a number between 1 and 9, "." or "#" (without quotes).
In the first and only line, print a single number - the smallest number of moves required for the queen to
reach the exit square.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 24점 | n, \(m \le 5\) |
2 | 32점 | There won’t be any portals on the board. |
3 | 18점 | n, \(m \le 500\) |
4 | 36점 | No additional constraints. |
4 4
S..1
####
1.#E
....43 3
S..
.#.
..E25 4
S.21
####
2##1
###.
E..#4Clarification of the third example: Queen Sofia will move to number 1 in the 1st row in her first
move (note that there is no blocked square between S and 1, so this move is indeed possible). She will
then teleport to the second number 1 in the matrix and will make 3 more moves to the exit square. With
these moves, she has indeed made the fewest number of moves needed from the starting to the exit square.