P14469 [COCI 2025/2026 #1] 皇后 / Kraljica

本题满分 $110$。

有一块 $n$ 行 $m$ 列的国际象棋棋盘。你要操作皇后（queen）从起点移动到终点。棋盘有如下几种类型的格子： - $\texttt{S}$：起点。 - $\texttt{E}$：终点。 - $\texttt{\#}$：障碍。 - $\texttt{.}$：空格子。 - $\texttt{1}\sim \texttt{9}$：传送门（见下）。 棋盘上有若干个传送门：$\texttt{1}\sim \texttt{9}$ 中的若干个数字会在棋盘上出现**两次**。当皇后到达传送门时，**可以**选择移动到棋盘上另一个写着相同数字的传送门处，这个操作不计入步数。传送之后的第一次移动同样计入步数，无论方向如何。 皇后的移动规则和国际象棋类似：在一步中，可以将皇后移动到同一行，同一列或同一对角线上的任意一个**未被障碍物阻挡**的格子（换言之，这一步起点到终点连的线段经过的格子不能有障碍物，包括起终点）。 求出从起点到终点的最小步数，或报告无解。

第一行，两个正整数 $n,m(1 \leq n,m\leq 1000)$。 接下来 $n$ 行，第 $i$ 行一个长度为 $m$ 的字符串，字符集为 $\{\texttt{S},\texttt{E},\texttt{\#},\texttt{.},\texttt{1}\sim \texttt{9}\}$，其中第 $i$ 行的第 $j$ 个字符 $c_{i,j}$ 表示第 $i$ 行第 $j$ 列的格子类型。

若无解，输出一行一个 $\texttt{-1}$。 否则输出一行一个正整数，表示答案。

### 样例解释 **样例三解释**：走到传送门 $1$ 处，传送；然后用三次操作走到终点。可以证明 $4$ 是最少步数。 ### 子任务 - $\text{Subtask 1 (24 pts)}$：$n,m\le 5$。 - $\text{Subtask 2 (32 pts)}$：无传送门。 - $\text{Subtask 3 (18 pts)}$：$n,m\le 500$。 - $\text{Subtask 4 (36 pts)}$：无额外限制。