题目背景

在一个 $n \times m$ 的方格迷宫中，你从起点出发，目标是到达终点。迷宫中存在无法通过的障碍物，你每次只能向上下左右四个相邻的方格移动一步。

题目描述

给定一个 $n \times m$ 的矩阵，包含以下字符：

• 's'：起点（有且仅有一个）
• 't'：终点（有且仅有一个）
• '.'：通路（可以通过）
• '#'：障碍物（不可通过）

请计算从起点到终点的最小移动步数。如果无法到达终点，请输出 $-1$。

输入格式

第一行包含两个整数 $n, m$ ($1 \leq n, m \leq 1000$)。 接下来的 $n$ 行，每行包含一个长度为 $m$ 的字符串，由 's', 't', '.', '#' 组成。

输出格式

一个整数，表示最短路径长度。若无法到达，输出 $-1$。

样例

3 4
s..#
.#..
...t

5

样例解释

路径为 $(0,0) \to (0,1) \to (0,2) \to (1,2) \to (2,2) \to (2,3)$，总步数为 5。