building.cpp

迷宫问题

#include <iostream>
#include <fstream>
#include "building.h"
#include "cell.h"
using namespace std;

const char OPEN=' ', WALL='X', INITIAL='S', HELIPAD='H', PARKING='P', UPSTAIR='^', DOWNSTAIR='v',
				NORTH='n', SOUTH = 's', EAST='e', WEST='w', DEADLOCK='L'; 

Building::Building(string filename)				//在构造函数中读入地图，默认参数filename为“building.txt"
{	
	ifstream infile;	
	infile.open(filename.c_str());
	if(filename!="building.txt"
		&&infile.fail())
	{
		cout<<"INCORRECT INFILE.\n";
		exit(1);
	}
	col_size=0;

	int floors=1;
	infile>>col_size>>floors;
	col_size+=2;							//用map[][]记录地图时，在每层楼的四周加一层墙，行数和列数分别加2
	row_size=col_size*floors;
	
	map= new char*[row_size];
	char str[30];			//used to read characters not representing squares
	char c;			//same as above
	infile.get(c);		//跳过楼层数字后的回车键
	
	for(int i=0; i<floors; i++)
	{
		//infile.getline(str,30);	//跳过写楼层的一行
		
		map[col_size*i]=new char[col_size+1];
		map[col_size*i+col_size-1]=new char[col_size+1];
		for(int col=0; col<=col_size-1; col++)		//一层楼的上边和底边填充为墙
		{
			map[col_size*i][col]=WALL;
			map[col_size*i+col_size-1][col] = WALL;
		}

		for (int k=1; k<=col_size-2; k++)
		{
			map[i*col_size+k]=new char[col_size+3];
			map[k+i*col_size][0]=WALL;			//一层楼的左边和右边填充为墙
			map[k+i*col_size][col_size-1]=WALL;



			for(int j=1; j<col_size-1; j++)
			{
				infile.get(map[k+i*col_size][j]);
				if (map[k+i*col_size][j]=='#')
				{
					infile.getline(str,30);			//跳过以“#”标识的注释行
					j--;
				}

				if (map[k+i*col_size][j]=='\n')					
				{
					cout<<"INSUFFICIENT CELLS IN THE BUIDLING.\n";
					exit(1);
				}
				if (map[k+i*col_size][j]==INITIAL)
					initialSquare=Cell(k+i*col_size, j);
				if (map[k+i*col_size][j]==HELIPAD)
					exitSquare[0]=Cell(k+i*col_size, j);
				if (map[k+i*col_size][j]== PARKING)
					exitSquare[1]=Cell(k+i*col_size, j);
			}


			infile.getline(str,30);		//跳过多余的字符和回车键
		}
	}
	infile.close();
	currentSquare=initialSquare;
}

void Building::printMap(string filename) const 
{
	ofstream outfile;
	outfile.open(filename.c_str());		
	map[initialSquare.x][initialSquare.y]='S';
	map[exitSquare[0].x][exitSquare[0].y]='H';
	map[exitSquare[1].x][exitSquare[1].y]='P';

	for(int i=0; i<row_size/col_size; i++)
	{
		cout<<"#floor "<<row_size/col_size-i<<endl;
		outfile<<"#floor "<<row_size/col_size-i<<endl;
		
		
		for(int k =1; k<= col_size-2; k++)
		{
			for(int j=1; j<col_size-1; j++)
			{	
				if (map[k+i*col_size][j]=='0'||map[k+i*col_size][j]==DEADLOCK)				//Queue_Building的escape函数将曾加入队列的所有格子标记了'0'，Stack_Building的escape函数将死路标记为DEADLOCK,
					map[k+i*col_size][j]=OPEN;																// 此处输出地图，还原为空格(OPEN)输出
				if (map[k+i*col_size][j]=='<')
					map[k+i*col_size][j]='^';	
				if (map[k+i*col_size][j]=='>')
					map[k+i*col_size][j]='v';	
				
				outfile<<map[k+i*col_size][j];
				cout<<map[k+i*col_size][j];
			}
			outfile<<endl;
			cout<<endl;
		}
	}
}


////Derived class Stack_Building, using stacks to impement escape()
/////////////////////////////////////////////////////////////////////////////////////

Stack_Building::Stack_Building(string filename): Building(filename)
{}

bool Stack_Building::pushUnvisited(int row, int col)
{
	if( map[row][col] == OPEN || map[row][col] == UPSTAIR || map[row][col]== DOWNSTAIR 
		|| map[row][col]== HELIPAD || map[row][col]== PARKING)
	{
		unvisited.push(Cell(row, col));
		return 1;
	}else
		return 0;
}
bool Stack_Building::deadWay(int x, int y)
{
	if (map[x][y-1]==OPEN||map[x][y-1]==UPSTAIR||map[x][y-1]==DOWNSTAIR||map[x][y-1]==HELIPAD||map[x][y-1]==PARKING)
		return 0;
	else if(map[x][y+1]==OPEN||map[x][y+1]==UPSTAIR||map[x][y+1]==DOWNSTAIR||map[x][y+1]==HELIPAD||map[x][y+1]==PARKING)
		return 0;
	else if(map[x+1][y]==OPEN||map[x+1][y]==UPSTAIR||map[x+1][y]==DOWNSTAIR||map[x+1][y]==HELIPAD||map[x+1][y]==PARKING)
		return 0;
	else if(map[x-1][y]==OPEN||map[x-1][y]==UPSTAIR||map[x-1][y]==DOWNSTAIR||map[x-1][y]==HELIPAD||map[x-1][y]==PARKING)
		return 0;
	else
		map[x][y]=DEADLOCK;
		return 1;
}

bool Stack_Building::escape()
{
	int row, col;
	route.push(initialSquare);	
	
	while( !(currentSquare == exitSquare[0] )&& !(currentSquare == exitSquare[1]))
	{
		row = currentSquare.x;
		col = currentSquare.y;
		do
		{
			if (map[row][col] == UPSTAIR&&row>col_size)
			{
				map[row][col]='u';
				row = row- col_size;
				currentSquare=Cell(row, col);
				route.push(currentSquare);
			}
			if (map[row][col] == DOWNSTAIR&&row_size>row+col_size)
			{
				map[row][col]='d';
				row=row+col_size;
				currentSquare=Cell(row, col);
				route.push(currentSquare);
			}
		}while( (map[row][col] == UPSTAIR&&row>col_size)||(map[row][col] == DOWNSTAIR&&row_size>row+col_size));

		do
		{
			row=currentSquare.x;
			col=currentSquare.y;

			if(pushUnvisited(row,col-1))			//检查四个方向是否可通，若可通，标记当前格移动方向并将下一格加入未访问的栈，选路时优先级为n,e,s,w
				map[row][col]=WEST;
			if(pushUnvisited(row+1,col))
				map[row][col]=SOUTH;
			if(pushUnvisited(row,col+1))
				map[row][col]=EAST;
			if(pushUnvisited(row-1,col))
				map[row][col]=NORTH;

			if(deadWay(row,col))//map[row][col]==OPEN||map[row][col]==DEADLOCK)				//若没有可通路径
			{			
				if(route.empty())
				{
					cout<<"Failure\n";
					return 0;
				}

				route.pop();
				currentSquare=route.top();				//退回上一格,将上一格标记清空
				map[currentSquare.x][currentSquare.y]=OPEN;		
				
				if(!deadWay(currentSquare.x,currentSquare.y))
					pushUnvisited(currentSquare.x,currentSquare.y);
			}
		}while(deadWay(currentSquare.x,currentSquare.y));			//此循环至，找到有通路的格为止

		if(unvisited.empty())
		{
			cout<<"Failure\n";
			return 0;
		}
		currentSquare=unvisited.pop();
		route.push(currentSquare);
	}
	return 1;
}



////Derived class Queue_Building, using queues to impement escape()
////////////////////////////////////////////////////////////////////////////////////////

Queue_Building::Queue_Building(string filename): Building(filename)
{}

bool Queue_Building::escape()
{
	unvisited=ArrayQueue<Cell>((row_size-2*col_size)*(col_size-2));							//基于数组的队列unvisited用于存放可以到达的格子（open, upstair, or downstair)
																											//每个格子不能重复入列，因此数组大小不会超过(row_size-2*col_size)*(col_size-2)
	unvisited.enqueue(Cell(initialSquare));

	do 
	{
		if (unvisited.isEmpty())								//unvisited被取空，说明没有可通路径
		{
			cout<<"Failure\n";
			return 0;
		}
		else
		{
			currentSquare= unvisited.dequeue();				//取队头格子为currentSquare
			int row=currentSquare.x;
			int col=currentSquare.y;

			if(map[row][col]=='<'&& row>col_size)			//case 1: currentSquare is upstair(make sure won't go beyond the map scope)
			{
				unvisited.enqueue(Cell(row-col_size, col, unvisited.head-1));
				if(map[row-col_size][col]==OPEN)
					map[row-col_size][col]='0';
				if(map[row-col_size][col]==UPSTAIR)
					map[row-col_size][col]='<';
			}
			else if(map[row][col]=='>'&&row_size>row+col_size)		//case 2: downstair
			{
				unvisited.enqueue(Cell(row+col_size,col, unvisited.head-1));
				if(map[row+col_size][col]==OPEN)
					map[row+col_size][col]='0';
				if(map[row+col_size][col]==UPSTAIR)
					map[row+col_size][col]='<';
			}
			else																									//case 3: currentSquare is an open square or invalid up/down stair, check the 4 directions				
			{
				if (map[row][col]==DOWNSTAIR||map[row][col]==UPSTAIR)		//special case: invalid up/down stair
					map[row][col]='0';

				if(map[row-1][col]==OPEN)				//检查上方，若上方方格为空
				{
					unvisited.enqueue(Cell(row-1, col, unvisited.head-1));
					map[row-1][col]='0';																		//所有曾加入队列的格子用‘0’标记以避免重复入列
				}else if(map[row-1][col]=='v')
				{
					unvisited.enqueue(Cell(row-1, col, unvisited.head-1));
					map[row-1][col]='>';
				}else if(map[row-1][col]=='^')
				{
					unvisited.enqueue(Cell(row-1, col, unvisited.head-1));
					map[row-1][col]='<';
				}
				else if(map[row-1][col]==PARKING||map[row-1][col]==HELIPAD)			//若上方为出口，直接跳出循环
				{
					unvisited.enqueue(Cell(row-1, col, unvisited.head-1));
					break;
				}

				if(map[row][col+1]==OPEN)					//检查右方
				{
					unvisited.enqueue(Cell(row, col+1, unvisited.head-1));
					map[row][col+1]='0';
				}else if(map[row][col+1]=='v')
				{
					unvisited.enqueue(Cell(row, col+1, unvisited.head-1));
					map[row][col+1]='>';
				}else if(map[row][col+1]=='^')
				{
					unvisited.enqueue(Cell(row, col+1, unvisited.head-1));
					map[row][col+1]='<';
				}
				else if(map[row][col+1]==PARKING||map[row][col+1]==HELIPAD)
				{
					unvisited.enqueue(Cell(row, col+1, unvisited.head-1));
					break;
				}

				if(map[row+1][col]==OPEN)				//检查下方
				{
					unvisited.enqueue(Cell(row+1, col, unvisited.head-1));
					map[row+1][col]='0';
				}else if(map[row+1][col]=='v')
				{
					unvisited.enqueue(Cell(row+1, col, unvisited.head-1));
					map[row+1][col]='>';
				}else if(map[row+1][col]=='^')
				{
					unvisited.enqueue(Cell(row+1, col, unvisited.head-1));
					map[row+1][col]='<';
				}
				else if(map[row+1][col]==PARKING||map[row+1][col]==HELIPAD)
				{
					unvisited.enqueue(Cell(row+1, col, unvisited.head-1));
					break;
				}

				if(map[row][col-1]==OPEN)				//检查左方
				{
					unvisited.enqueue(Cell(row, col-1, unvisited.head-1));
					map[row][col-1]='0';
				}else if(map[row][col+1]=='v')
				{
					unvisited.enqueue(Cell(row, col-1, unvisited.head-1));
					map[row][col-1]='>';
				}else if(map[row][col-1]=='^')
				{
					unvisited.enqueue(Cell(row, col-1, unvisited.head-1));
					map[row][col-1]='<';
				}
				else if(map[row][col-1]==PARKING||map[row][col-1]==HELIPAD)
				{
					unvisited.enqueue(Cell(row, col-1, unvisited.head-1));
					break;
				}
			}
		}
	}while( currentSquare!= exitSquare[0] && currentSquare!=exitSquare[1]);		//循环至取出的队头元素为出口（或队列被取空时跳出循环）

	//////////////////////////////////////////////回溯，找出最短路径并标记方向
	int index_of_route=unvisited.rear;
	while(index_of_route!=0)
	{
		int *pre_x, *pre_y;														//x、y为指向前驱格子的列和行坐标值的指针
		pre_x= &unvisited.arr[unvisited.arr[index_of_route].pre].x;
		pre_y= &unvisited.arr[unvisited.arr[index_of_route].pre].y;				
		char c= map[*pre_x][*pre_y];										//根据前驱格子上的标记和与当前格子坐标的关系确定方向并标记
		switch (c)								
		{		
			case '0':
				{
					if (unvisited.arr[index_of_route].x< *pre_x)
						map[*pre_x][*pre_y]='n'; 
					else if (unvisited.arr[index_of_route].x> *pre_x)
						map[*pre_x][*pre_y]='s'; 
					else if (unvisited.arr[index_of_route].y< *pre_y)
						map[*pre_x][*pre_y]='w'; 
					else if (unvisited.arr[index_of_route].y> *pre_y)
						map[*pre_x][*pre_y]='e'; break;
				}
			case '<':
				map[*pre_x][*pre_y]='u'; break;
			case '>':
				map[*pre_x][*pre_y]='d'; break;
		}

		index_of_route=unvisited.arr[index_of_route].pre;		//回溯一格
	}		
																					//循环至找到起始点结束
	return 1;																	
}

////////////////////////////////////////////////////上一个子类已经达到较高的效率，因此opt算法与queue相同，p1里没有用到这个子类

Opt_Building::Opt_Building(string filename): Building(filename)
{}
bool Opt_Building::escape()
{
	return 0;
}

extern Stack_Building sBuilding=Stack_Building ("building.txt");
extern Queue_Building qBuilding=Queue_Building("building.txt");
extern Opt_Building oBuilding=Opt_Building("building.txt");

extern Building *get_Stack()
{
	Building *p = &sBuilding;
	return p;
}
extern Building *get_Queue()
{
	Building *p = &qBuilding;
	return p;
}
extern Building *get_Opt()
{
	Building *p = &oBuilding;
	return p;
}