一聚教程网:一个值得你收藏的教程网站

热门教程

计算各点到源点的最短距离

时间:2022-07-02 10:57:14 编辑:袖梨 来源:一聚教程网


比较好.灵.巧的算法,大家不妨看一看,蛮爽的!!^_^^_^

 

#include
#include
using namespace std;
#include
#include

//宏定义
#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:"< 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 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   iend   = (curnode.x+K>N-1) ?