相邻项序列

相邻项序列  问题描述： 对于一个N*N（N≤100）的正整数矩阵M，存在从M[A1，B1]开始到M[A2，B2]结束的相邻项序列。两个项M[I，J]和M[K，L]相邻的条件是指满足如下情况之一：（1）I=K±1和J=L；（2）I=K和J=L±1。先要求你从文件中读入矩阵M及K（K≤4）组M[A1，B1]和M[A2，B2]，求一相邻项序列，使得相邻项之差的绝对值之和为最小。 输入格式及样例： 4                  //表示矩阵M的大小       1   9   6   12     //每行有M个数据，共M行 8   7   3   5 5   9   11  11 7   3   2   6 2                  //表示有K组数据 4   1   1   4      //表示A1，B1及A2，B2的值，共K行 2   2   3   4    输出格式及样例： 1  17               //表示第1组数据相邻项之差的绝对值之和的最小值为17 7  5  8  7  9  6  12    //表示第1组数据的相邻序列 2  4                 //表示第2组数据相邻项之差的绝对值之和最小值为4 7  9  11  11          //表示第2组数据的相邻序列 　   算法分析： 本题若将相邻的两个数看成是两个顶点，两个数差的绝对值作为权，则问题转化为图论中的求两顶点间的最短路问题。 对于有向图D=（V，A），弧a=（Vi,Vj）,相应地有权W（a）=Wij，对有向图D中两个顶点Vs,Vt，设P是D中从Vs到Vt的一条路，定义路P的权是P中所有弧的权之和，记作W（p），所谓最短路问题就是在所有从Vs到Vt的路中，找出一条权最短的路，即求一条从Vs到Vt的路P0，令：            W（P0）=min(p) 对于所有Wij>=0，即所有的权为非负值时，求最短路通常使用标号法。 所谓标号法的基本思想是从Vc出发，逐步地向外探寻最短路。在执行过程中，与每个点对应，记录下一个数（称为这个点的标号），它或者表示从Vs到该点的最短路的权（称为P标号），或者表示这个权的上界（称为T标号），具体做法是每扩展一步，就将一个具T标号的点改具P标号的点，从而使有向图D中具P标号的顶点数增多一个。如此一步步执行下去，就可求出从Vs到各点的最短路。 为简便起见，我们可以称从M[I，J]到M[K，L]的相邻项之差的绝对值之和最小的相邻项序列为从M[I，J]到M[K，L]的“最优序列”。这样便可用标号法来求得从起点M[A1，B1]到矩阵M的其它各项的“最优序列”。 设SUM[I，J]为从M[A1，B1]到M[I，J]的“最优序列”的相邻项的绝对值之和。有： SUM[I，J]=MIN SUM[K，L]+ABS（M[I，J]-M[K，L]）{I=K±1且J=L，或I=K且J=L±1} 通过这一式子，可以利用标号法来求得从M[A1，B1]到M[A2，B2]的最优序列。 在标号法中，每一次扩展都要寻找一个项M[I，J]，其中： ① M[I，J]是未改为P的标号的点； ② SUM[I，J]=MIN SUM[K，L]{K，L∈[1，N]，且M[K，L]是未改为P标号的点。 这一步若采用二重循环来求则非常耗时。所以考虑采用一个队列来存储矩阵中待扩展的项，使得该队列的各项的SUM值地由小到大排列的。扩展时，只要移动队列的首指针即可：生成的新的待扩展的项，可以将其插入到队列中的适当位置，使插入后队列的各项的SUM值仍是从小到大排列。为了较方便地插入新的待扩展的项，采用指针结构来存储这个队列。 具体算法描述：   定义一个POINT类型来记录待扩展的项：    point=^xy; xy=record    x,y:byte;    next:point; end; 其中X，Y为该项在矩阵中的坐标，NEXT为指针类型，以记录其在队列中的后继结点。 1、  置SUM[I，J]为∞（I<>A1或J<>B1），置SUM[A1，B1]为0； 2、  首指针F后移一位； 3、  若F^.X=B2且F^.Y=A2，则已找到从M[A1，B1]到M[A2，B2]的“最优序列”，反向链接、打印所经过的路径并转6，否则继续4； 4、  从M[F^.Y,F^.X]向上下左右四个方向扩展，现设向M[NODE1^.Y,NODE1^.X](NODE1^.Y=F^.Y±1且NODE1^.X=F^.X，或NODE1^Y=F^.Y且NODE1^.X=F^.X±1)扩展： a)     SUM1：=SUM[F^.Y,F^.X]+ABS(M[F^.Y,F^.X]-M[NODE1^.Y,NODE1^.X]); b)      若SUM1

斑竹的数据结构学得真好

佩服佩服！