desert.cpp

该算法设计短小精悍

// Desert.cpp: implementation of the Desert class.
//
//////////////////////////////////////////////////////////////////////

#include "Desert.h"
#include <math.h>
//////////////////////////////////////////////////////////////////////
// Name:		Desert.cpp
// author:		Zhang Zhenjie
// Date:		2004.9.27
// Description: the implementation of the class Desert
//				It's the shortest path algorithm in this class
// version:     1.0
//////////////////////////////////////////////////////////////////////

Desert::Desert()
{
	int temp;

	//read the desert width and survive distance
	vertexNum = 0;
	cin >> desertWidth;
	cin >> surviveDistance;

	//initialize the array
	//the length can not be longer than width^3
	impossibleLength = desertWidth*desertWidth*desertWidth;
	//the number of vertex can no more than width^2
	x_cor = new int[desertWidth*desertWidth];
	y_cor = new int[desertWidth*desertWidth];


	//record all the verices
	for(int i = 0; i < desertWidth; i++)
	{
		for(int j = 0; j < desertWidth; j++)
		{
			cin >> temp;
			
			switch(temp){
			case 1:
				x_cor[vertexNum] = i;
				y_cor[vertexNum] = j;
				startVertex = vertexNum;
				vertexNum++;
				break;
			case 2:
				x_cor[vertexNum] = i;
				y_cor[vertexNum] = j;
				vertexNum++;
				break;
			case 3:
				x_cor[vertexNum] = i;
				y_cor[vertexNum] = j;
				endVertex = vertexNum;
				vertexNum++;
				break;
			default:
				break;
			}
		}
	}
}

Desert::~Desert()
{
	//destory the allocated space
	delete [] x_cor;
	delete [] y_cor;
	delete [] isComplete;
	delete [] bestSolution;

	for(int i = 0; i < vertexNum; i++)
		delete [] distanceMatrix[i];

	delete [] distanceMatrix;
}


void Desert::GetDistance()
{
	isComplete = new bool[vertexNum];
	bestSolution = new int[vertexNum];

	distanceMatrix = new int*[vertexNum];
	for(int i = 0; i < vertexNum; i++)
		distanceMatrix[i] = new int[vertexNum];


	for(i = 0; i < vertexNum; i++)
	{
		isComplete[i] = false;

		//initialize the origianl distance to an impossible value
		bestSolution[i] = impossibleLength;

		//use L_1 distance
		for(int j = 0; j < vertexNum; j++)
			distanceMatrix[i][j] = abs(x_cor[i]-x_cor[j])+abs(y_cor[i]-y_cor[j]);
	}

	//at the beginning, only the start point is finished, and the distance to himself is 0
	isComplete[startVertex] = true;
	bestSolution[startVertex] = 0;
}

int Desert::GetSoltion()
{
	int tempBest;
	int tempVertex;

	while(1)
	{
		//the current best solution must be smaller than the impossible value
		tempBest = impossibleLength;

		//search all the vertices which has not had final conclusion
		//the value of the possible solution of a vertex should be renewed if 
		//we add a new vertex to the complete set
		for(int j = 0; j < vertexNum; j++)
		{
			if(j != startVertex && !isComplete[j])
			{
				if(distanceMatrix[startVertex][j] <= surviveDistance)
				{
					int temp = bestSolution[startVertex] + distanceMatrix[startVertex][j];
					if(temp < bestSolution[j])
					{
						bestSolution[j] = temp;
					}
				}
	
				//if it's the best solution we have ever seen in this round
				if(bestSolution[j] < tempBest)
				{
					//update the best solution and vertex
					tempBest = bestSolution[j];
					tempVertex = j;
				}

			}
		}
		
		//if no new vertex is reachable in this round
		//there's no new path to the destination, the computation failed
		if(tempBest == impossibleLength)
			return -1;

		//if we have ascertain the solution to the destination
		//no need to further the computation, just return the solution on the destination
		if(tempVertex == endVertex)
			return bestSolution[tempVertex];
		
		//update the complete property of the vertex found in this round
		isComplete[tempVertex] = true;

		//move the start vertex to the new one, and update again
		startVertex = tempVertex;
	}
}