a2.cpp

第二届全国高校 BBS 程序开发大赛算法组

#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;
}