Description

有一个6*6大小的荆棘之地，每一个格子上都有一个数值，现在给予冒险家一个随机出生坐标和终点坐标，请你找出起始位置到终点位置代价最小的路径：

1.只能上下左右四个方向进行移动

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

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

4.初始状态为1，每走1步，状态按如下公式变化：(走这步的代价mod 4 + 1)

Input Format

每组数据一开始为6*6的矩阵，然后四个整数表示起始坐标和终止坐标。

横纵坐标均从0开始.

Output Format

输出穿过荆棘的最小代价。

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 5 5​

23​

Hint

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

Source

spfa,dfs,dijkstra