#include "stdio.h"#include "math.h"#define N 4#define M 6void minDire(int i,int j);//多个方向的最短路void roadPath(int i,int j);//画出任意坐标点到终点最短路径的路线
int d[N+2][M+2],road[N+2][M+2][3][3],i,j,k;//d[][]是坐标数据,road[N+2][M+2][3][3]是记录行走方向的数组double juli[N+2][M+2][3][3],c[N+2][M+2];int dire[8][2]={{1,0},{1,1},{1,-1},{-1,0},{-1,1},{-1,-1},{0,1},{0,-1}};//方向void main(){ for (i=0;i<=N+1;i++) { for (j=0;j<=M+1;j++) { c[i][j]=10000; d[i][j]=0;//初始化 for (int i1=0;i1<=2;i1++) { for(int j1=0;j1<=2;j1++) { road[i][j][i1][j1]=0; //juli[i][j][0][0]代表（-1，-1）这个方向，juli[i][j][1][2]代表（0，1）这个方向，其余类推 juli[i][j][i1][j1]=0; } } } } d[1][1]=d[1][2]=d[1][3]=d[1][6]=d[2][1]=d[2][4]=d[2][5]=d[2][6]=1; //原数组初始化 d[3][1]=d[3][2]=d[3][4]=d[3][5]=d[4][2]=d[4][3]=d[4][6]=1;
for (i=1;i<=N;i++) { for (j=1;j<=M;j++) { for (k=0;k<8;k++) { //为每个坐标赋各个方向距离值，只有2点都为1的时候才有距离 if (d[i][j]!=0) { //x坐标变大，j变大，y坐标变大，i变小！ if (d[i-dire[k][1]][j+dire[k][0]]!=0)//保证dire[k][0]+1，dire[k][1]+1非负 { juli[i][j][dire[k][0]+1][dire[k][1]+1]=sqrt(dire[k][0]*dire[k][0]+dire[k][1]*dire[k][1]); //printf("%.2f ",sqrt(dire[k][0]*dire[k][0]+dire[k][1]*dire[k][1])); // printf("juli[%d][%d][%d][%d]=%.2f ",i,j,dire[k][0]+1,dire[k][1]+1,juli[i][j][dire[k][0]+1][dire[k][1]+1]); }
} } } } //我的动态规划采取波浪外推得方式，就是令终点周围的点先获取最短路，然后再类似往外层扩散 i=N;j=M; int t=0,m_t; if (N<M) m_t=N; else m_t=M; //开始按照正方形往外推 while(t<m_t) { i=N-t; for (j=M;j>=M-t;j--) { if (i==N&&j==M){ c[i][j]=0;} else { minDire(i,j); } } j=M-t; for (i=N;i>=N-t;i--) { if (i==N&&j==M){ c[i][j]=0;} else { minDire(i,j); } } t++; } //然后一排一排的往外推 if (N<M) { for(j=M-N;j>=1;j--) for (i=N;i>=1;i--) { minDire(i,j); }
} else { for(i=N-M;i>=1;i--) for (j=M;j>=1;j--) { minDire(i,j); } }
printf("矩阵中任意一点到终点的最短距离分别为：/n"); for (i=1;i<=N;i++) { for (j=1;j<=M;j++) { printf("c[%d][%d]=%.2f ",i,j,c[i][j]); } printf("/n"); } roadPath(3,1);}
//多方向的最短路void minDire(int i,int j){ double min=1000; for (int k=0;k<8;k++) { if (juli[i][j][dire[k][0]+1][dire[k][1]+1]) { if( (c[i-dire[k][1]][j+dire[k][0]]+juli[i][j][dire[k][0]+1][dire[k][1]+1]) <min) { min=c[i-dire[k][1]][j+dire[k][0]]+juli[i][j][dire[k][0]+1][dire[k][1]+1]; c[i][j]=min; //先对原来存储的清0 for (int i1=0;i1<=2;i1++) { for(int j1=0;j1<=2;j1++) { road[i][j][i1][j1]=0; } } road[i][j][dire[k][0]+1][dire[k][1]+1]=1; } } }}//画出任意坐标点到终点最短路径的路线void roadPath(int i,int j){ int flag=0,i1,j1; for (i1=0;i1<=2;i1++) { for(j1=0;j1<=2;j1++) { if (road[i][j][i1][j1]==1) { printf("(%d,%d)->(%d,%d),",i,j,i-(j1-1),j+(i1-1)); if (i-(j1-1)!=N||j+(i1-1)!=M) { roadPath(i-(j1-1),j+(i1-1)); } } } }
}
