问题1186--破阵

1186: 破阵

[命题人 : ]
时间限制 : 2.000 sec  内存限制 : 128 MB

题目描述

在你的帮助之下,Miaoyao成功完成了他的编程作业,于是他又开始了一局新的游戏。这次他玩的游戏背景为一个仙侠世界。当前,Miaoyao被困在一个阵法中。阵法可以视为一个nm列的矩形区域,每个小格都各有玄机,一旦踏入就需要耗费一定量的灵气抵御(离开后重新进入,同样需要消耗灵气)。还有一些位置暗藏杀阵,不可进入。Miaoyao每次只能向上下左右这四个方向移动一格。阵法包含k个阵眼和一个阵核。想要破阵而出,必须要在每个阵眼处各放置一件法宝,然后再从阵核离阵。显然,Miaoyao不希望消耗过多的灵气,于是他想要你帮助他算出破阵所需消耗的最小灵气值。

输入

第一行两个整数n,m。

接下来n行,每行m个整数,第i行第j列的整数wi j 表示到达该位置所消耗的灵气值。若wi j为-1,则表示该点不可进入。

接下来一行,一个整数k。

接下来k行,每行两个整数r,c,表示阵眼所在的行列。

接下来一行,四个整数sr,sc,tr,tc,分别表示起点所在的行、起点所在的列、阵核所在的行、阵核所在的列。

输入保证wsr sc=0,阵眼各不相同、不与阵核重合,且阵眼与阵核均不在无法进入(即wij=-1)的格子。


输出

若能破阵,则输出一个整数,表示最小的灵气消耗,否则输出"Impossible"(不含引号)。

样例输入 Copy

5 5
0 2 -1 -1 -1
-1 3 -1 -1 -1
-1 1 2 3 4
-1 4 3 2 1
-1 -1 -1 -1 5
2
3 3
4 2
1 1 5 5

样例输出 Copy

24

提示

1<=n,m<=50

-1<=wij<=1000

1<=k<=9

1<=r,sr,tr<=n

1<=c,sc,tc<=m

来源/分类