比较好.灵.巧的算法,大家不妨看一看,蛮爽的!!^_^^_^
#include <iostream> #include <deque> using namespace std; #include <memory.h> #include <math.h>
//宏定义 #define MAZE(m,n) maze[(m)*N+(n)] #define DISTANCE(m,n) distance[(m)*N+(n)]
//结构定义 typedef struct _node { int x,y,layernum; } node;
void main() { //数据定义与输入,maze中存储输入矩阵,distance中存储矩阵各节点到出发点的最短距离(初始化为-1) char *maze; int *distance; int N,K,start[2],end[2]; cout<<"Input The numbers:"<<endl; cin>>N>>K; maze = new char[N*N]; distance = new int[N*N]; int temp; for (int i = 0; i < N*N; ++i){ distance[i] = -1; cin>>temp; maze[i] = temp; }
//找出起点和终点 temp = (char *)memchr(maze,2,N*N)-maze; start[0] = temp/N; start[1] = temp%N; temp = (char *)memchr(maze,3,N*N)-maze; end[0] = temp/N; end[1] = temp%N;
/****************计算各点到源点的最短距离************************************************** 算法原理:对由所有绿洲以及起点/终点构成的图,运用广度搜索进行遍历, 同时动态更新图中当前遍历node以及其子节点对应的distance矩阵数据项, 遍历完毕后,distance矩阵中存储的即为各个node到起点的最佳路线距离。 ******************************************************************************************/ deque<node> nodequeue; node curnode,newnode; int curlayer = 0; int ibegin,iend,jbegin,jend,j,delt; DISTANCE(start[0],start[1]) = 0; curnode.x = start[0]; curnode.y = start[1]; curnode.layernum = 0; nodequeue.push_back(curnode); while (!nodequeue.empty()) { curnode=nodequeue.front(); while (curnode.layernum==curlayer) { nodequeue.pop_front(); ibegin = (curnode.x<K) ? 0 : (curnode.x-K); iend = (curnode.x+K>N-1) ? (N-1) : (curnode.x+K); for (i = ibegin; i<=iend; ++i){ delt = K-(int)abs(curnode.x-i); jbegin = (curnode.y<delt) ? 0 : (curnode.y-delt); jend = (curnode.y+delt>N-1) ? (N-1) : (curnode.y+delt); for (j = jbegin; j<=jend; ++j){ if (MAZE(i,j)>0){ temp = (int)abs(curnode.x-i)+(int)abs(curnode.y-j); if (DISTANCE(i,j)==-1){ newnode.x = i; newnode.y = j; newnode.layernum = curlayer+1; DISTANCE(i,j) = DISTANCE(curnode.x,curnode.y)+temp; nodequeue.push_back(newnode); } else { temp+=DISTANCE(i,j); if (DISTANCE(curnode.x,curnode.y)>temp) DISTANCE(curnode.x,curnode.y)=temp; } } } } if (nodequeue.empty()) break; else curnode = nodequeue.front(); } ++curlayer; }
//输出最短路径长度 cout<<DISTANCE(end[0],end[1]);
//回收内存 delete []distance; delete []maze; } 呵呵。。。^_^^_^(没有骗你吧...)
|