Problem 1017. -- Rescue

1017: Rescue

Time Limit: 5 Sec  Memory Limit: 63 MB
Submit: 8  Solved: 3
[Submit][Status][Web Board]

Description

小香猪的好友小乳猪不幸被大魔王抓住了!
大魔王住在位于猪国东北部的马戏团里,他的爱好之一就是搜寻各地的珍禽异兽,加以训练为他的马戏团服务。而小乳猪是远近闻名的才子,不仅能歌善舞,还在最近猪国的贺岁大片《哈里猪头》里面扮演了主角,自然成为了大魔王狩猎的对象。
虽说被大魔王抓住看起来不存在什么生命危险,但对于年轻的小乳猪来说,他的一生可能就这样被糟蹋掉了。更可怕的是,大魔王有一个弟弟——小魔王,和大魔王不同,他是生活在肉联厂里的!小乳猪一旦被他发现,后果将不堪设想……因此拯救小乳猪的行动迫在眉睫!
小香猪毅然决定担此重任。由于大魔王非常厉害,任何正面的冲突都无法避免伤亡,因此她决定偷偷地把小乳猪拯救出来。恰好大魔王在抓到小乳猪之后,又去寻找新的猎物了,暂时不在家里,因此小香猪打算趁大魔王不在这段时间,前往马戏团,救出小乳猪。但是,由于不知道大魔王何时会回来,因此,小香猪计划走最快的路线去拯救小乳猪。
行动前,小香猪研究了一下地图,她发现整个地图可以平均分割成N*N个小块,每个小块按照地形又可以分成以下7类:
1、 平地。平地上行走比较顺畅且具有较快的速度。
2、 山地。由于山路颠簸,因此一般情况下在山地上行走速度会比较慢。
3、 冰面。水结冰以后形成的路面,由于路面较滑,在冰面上行走速度会很快。
4、 河流。渡河是很费时间的。
5、 沼泽。这种地方是不可以去的,否则必死无疑!
6、 猪国。只有一个,位于地图的最西南角,也是小香猪出发的地方。
7、 马戏团。只有一个,位于地图的最东北角,也就是小香猪要到达的地方。
比如下面就是一个5*5的地图:

小香猪每次可从她当前所在的格子,走到东西南北4个方向的任意一个相邻格子中去(除非该格子是块沼泽)。
如果用上面的数字代表各类地形,那么这个地图又可以用一个N*N的矩阵描述如下:
2 3 3 3 7
4 2 2 5 5
4 4 2 3 3
2 4 4 4 2
6 1 1 4 2
现在,小香猪已经知道如果某个小块是地形i,她就需要Ti天才能走完这块地方,那么,要从猪国走到马戏团,最少需要多少走多少天呢?

Input

输入也许会有多组数据,每一组数据第一行为一个正整数N(3<=N<=1000),第二行为4个正浮点数T1、T2、T3、T4,分别表示走完每块平地、山地、冰面、河流所需的天数。接下来的N行中每行N个介于的正整数,以描述地图各块的地形,整个矩阵中只有第一行第N个数等于7,第N行第一个数等于6,其他位置的数均在1到5之间。
输入以一个0结尾。

Output

每一组数据对应一行输出,表示至少要走多少天才能到达马戏团,请将结果四舍五入为整数。如果小香猪无法走到目的地,则输出“Impossible!”(不含引号)。

Sample Input

5
1.0 2.5 0.4 4.3
2 3 3 3 7
4 2 2 5 5
4 4 2 3 3
2 4 4 4 2
6 1 1 4 2
3
1.5 4.0 1.0 5.0
1 1 7
5 5 2
6 1 5
0

Sample Output

12
Impossible!

HINT

第一个样例中,小香猪最后选择的路线是从西南角开始,向东2步、向北4步再向东2步到达马戏团。这样她所用的时间就是2*1.0+4.3+2*2.5+2*0.4=12.1≈12天。

Source

[Submit][Status]