问题4512--荆轲刺秦王

4512: 荆轲刺秦王

时间限制: 1 Sec  内存限制: 512 MB
提交: 0  解决: 0
[提交] [状态] [讨论版] [命题人:]

题目描述

时隔数年，刺客荆轲再次来到咸阳宫，试图刺杀嬴政。 咸阳宫的地图可以描述为一个 n 行 m 列的矩形,矩形中的点可以分为 4 种： (1)起点，也就是荆轲的所在点，在地图中用字符 S 代表。 (2)终点，也就是嬴政的所在点，在地图中用字符 T 代表。 (3)卫兵，在地图中用一个正整数 a_{i,j}代表。在这里，一个卫兵 (i,j) 可以观察到与他曼哈顿距离小于 a_{i,j}的点。也就是卫兵 (i,j) 可以观察到所有满足 ∣x-i∣+∣y-j∣

输入

第一行两个整数 n, m 接下来 n 行，每行 m 个元素。每个元素为字符 S、T、. 或者一个正整数 a_{i,j}，代表一个格点，具体含义详见题目描述。

输出

若荆轲无法到达秦王所在点，则输出一行一个 -1。 否则输出一行一个整数 t，代表所需的最短时间。

样例输入

(1)
5 4
. 1 T 1
. . . 2
. 1 . .
S . . .
1 . . .

(2)
8 6
. S . . . .
. . . . . .
. . . . . .
1 1 3 2 . 1
2 3 2 2 1 3 
3 2 4 1 4 3 
2 6 1 5 T 2 
8 1 6 3 2 10

样例输出

(1)

3
样例 1 解释
起点为 (4,1)，荆轲可以依次走到 (3,1), (2,2), (1,3) 到达终点。

(2)
-1

来源/分类

 

[提交] [状态]