有一个6*6的棋盘,棋盘的每个位置上都有一个数值,现在有一个起始位置和终止位置,请找出一个从起始位置到终止位置代价最小的路径:
1.只能沿上下左右四个方向移动。
2.总代价是每走一步的代价之和。
3.每步(从(a,b)到(c,d))的代价是(c,d)上的数值与(a,b)上的状态的乘积。
4.初始状态为 1,每走一步,状态按如下公式变化:(走这步的代价mod4)+1。
有一个6*6的棋盘,棋盘的每个位置上都有一个数值,现在有一个起始位置和终止位置,请找出一个从起始位置到终止位置代价最小的路径:
1.只能沿上下左右四个方向移动。
2.总代价是每走一步的代价之和。
3.每步(从(a,b)到(c,d))的代价是(c,d)上的数值与(a,b)上的状态的乘积。
4.初始状态为 1,每走一步,状态按如下公式变化:(走这步的代价mod4)+1。
一开始输入一个6*6的矩阵,然后四个整数表示起始坐标和终止坐标。
横纵坐标均从 0 开始,矩阵的左上角为 (0,0),右下角为 (5,5)。
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
13
【样例说明】
可以选择这样的一条路径:(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]