H. Kamen Rider and Labyrinth

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

新一轮的欲望大奖赛开始了！樱井景和也被选为假面骑士，成为了假面骑士太狸。

最初的任务是：寻宝游戏！

现在给出一个 $n$ 行 $m$ 列的地图，可以通行的道路为'.'，障碍物为'#'，太狸所在的位置为's'，需要寻找到的宝物的位置为't'。

太狸可以每步可以选择上、下、左、右四个方向，移动一格（若想要移动到的位置上有障碍物，则不能进行移动；若移动到的位置上刚好有宝物，则视为得到了宝物），问太狸最少需要多少步才能得到宝物？

如果太狸无论如何都得不到宝物，则输出 $-1$ 。

第一行两个整数 $n,m\;(1\leqslant n,m \leqslant 10^3)$ ，代表地图为 $n$ 行 $m$ 列的。第二行到第 $n+1$ 行，每行 $m$

个字符，数据保证只包含 's'、't'、'.'、'#'四种字符，且's'和't'保证出现且仅出现一次，字符的具体含义见题目描述。

一行一个整数，代表太狸寻找到宝物所需要的最少步数，若他无论如何都得不到宝物，则输出 $-1$

。

5 7
...s...
..#.#..
..#.##.
..#..t#
..#####