登录

题目A1176:反恐精英

题目描述

反恐精英是一款流行的射击游戏。
游戏中有两方势力:恐怖分子方和反恐精英方。你所扮演的是反恐精英,需要制服所有恐怖分子,并且拆除c4炸弹。
为了简化问题,假设所有恐怖分子已经被制服。剩下要做的,是在给定t(t<=1000)时间内,到达炸弹所在地点,拆除炸弹。即从起始点( sxsy )到达炸弹所在的( exey )点。
你会得到一个n*m(2<=nm<=100)的地图,地图上的每一个点用一个自然数表示,代表地图该点的高度。
每做一次移动,你能到与所在点相邻的,上、下、左、右的任意一个点。
有两种移动方式:
(1)普通移动:所耗费的时间是:|垂直高度差| + 1。
    例:从( x y)移动到( x+1 y),耗费时间为 | height(x y) - height(x+1 y) | + 1 
(2)跳跃移动:从高度较高的点移动到较低的点,可以直接跳跃,消耗1点的时间,并损失与高度差等量的血量。
    例:从( x y )移动到( x y+1),并且height(x y) > height(x y+1),那么你可以选择跳跃,耗费1点时间,height(x y) - heith(x y+1)血量
游戏开始你有100点血量,血量<=0时意味着死亡。

输入格式

输入的第一行是一个整数T(T<=20),代表有T组数据。
每组数据的第一行是七个整数nmsxsyexeyt,所表示的意义见题目描述。
下面紧跟n行,每行m个数字,height(i j)(<=100)表示点(ij)的高度。
地图最左上角的点为(00)点。

输出格式

如果你能在给定时间内到达目的地,输出 "Run Forrest run!",并在下一行输出到达目的地的最快时间。否则输出"Terrorists win!"。

输入样例
4
1 2 0 0 0 1 1
100 1
1 2 0 0 0 1 1
101 1
1 2 0 0 0 1 101
101 1
1 2 0 0 0 1 1
1 100
输出样例
Run, Forrest, run!
1
Terrorists win!
Run, Forrest, run!
101
Terrorists win!
请选择代码的语言:

0

通过

0

提交


时间
3 Sec
内存
128 MB
上传
admin

标签分类

动态规划

统计