Problem5716--棋盘游戏

5716: 棋盘游戏

Time Limit: 1.000 Sec  Memory Limit: 256 MB
Submit: 29  Solved: 11
[Submit] [Status] [Web Board] [Creator:]

Description

有一个6*6的棋盘,棋盘的每个位置上都有一个数值,现在有一个起始位置和终止位置,请找出一个从起始位置到终止位置代价最小的路径:

1.只能沿上下左右四个方向移动。

2.总代价是每走一步的代价之和。

3.每步(从(a,b)到(c,d))的代价是(c,d)上的数值与(a,b)上的状态的乘积。

4.初始状态为 1,每走一步,状态按如下公式变化:(走这步的代价mod4)+1。


Input

一开始输入一个6*6的矩阵,然后四个整数表示起始坐标和终止坐标。

横纵坐标均从 0 开始,矩阵的左上角为 (0,0),右下角为 (5,5)。


Output

输出最小代价



Sample Input

1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
0 0 3 3

Sample Output

13

HINT

【样例说明】

可以选择这样的一条路径:(0,0)→(0,1)→(0,2)→(0,3)→(1,3)→(2,3)→(3,3)

共6步,代价为:1 * 1 + 2 * 1 + 3 * 1 + 4 * 1 + 1 * 1 + 2 * 1 = 13

【数据范围】

矩阵内数值的取值范围[1,10]


Source/Category

 

[Submit] [Status]