提示: 欢迎访问OurACM平台。
Problem 1684 迷宫救美

Accept: 204    Submit: 1205
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

有一天香帅楚留香得知苏蓉蓉被人抓走就赶去营救,最后香帅来到了一间迷宫,已知苏蓉蓉的位置,不过她已经中了毒,香帅如何才能以最快的速度去救她呢?现在请你帮香帅想想方法。已知迷宫由一些高低不同的墙和一些走廊(其实也可以看成高度为0的墙)组成,由于香帅轻功了得,他可以越过一些墙,不过每越过一道墙,就要相应消耗相当于墙高度差的绝对值的内力,已知香帅内力一定,并且每从一格到相邻格(只包括上下左右相邻,不包括对角线相邻)要花费一个单位时间(无论是否翻墙),求香帅救得苏蓉蓉的最短时间。

Input

第一行输入R,W表示迷宫的大小R*W(2<=R,W<=20),所有位置坐标为 ([0,r-1],[0,w-1]);第二行输入E,a1,b1(0<=E<50)分别表示香帅的内力值和位置,第三行输入a2,b2 表示苏蓉蓉的位置。接着输入R行,每行W个数字(每个数字在0-9之间表示这一格的高度,0表示这一格是走廊,任两个数字之间无任何分隔符)。注:输入数据有多组。

Output

如果香帅能够救得苏蓉蓉,请输出最短的时间,否则输出"UNLUCKY!"(不包括""),一组数据一行。

Sample Input

4 4 30 1 0 3 3 7635 0401 3542 6730

Sample Output

5

Source

FOJ月赛-2009年2月- DZB

Submit  Back  Status  Discuss