maze.cpp

迷宫算法,自己编写

// maze.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include<iostream>
using namespace std;

//迷宫算法
//用数组构造迷宫(0表示是障碍，1表示可以通过）

#define INIT_SIZE 6
#define INCREMENT 3

class point
{
public:
	int x;
	int y;
};

//栈定义
typedef struct{
	point* top;
	point* base;
	int size;
}stack;

//初始化栈
bool InitStack(stack &s)
{
	s.base = (point*)malloc(INIT_SIZE*sizeof(point));
	if(!s.base)
		return false;
	s.top = s.base;
	s.size = INIT_SIZE;
	return true;
}
//入栈操作
bool Push(stack &s, point e)
{
	//追加栈空间
	if(s.top - s.base >= s.size)
	{
		s.base = (point*)realloc(s.base, (s.size + INCREMENT)*sizeof(point));
		if(!s.base)
			return false;
		s.top = s.base +s.size;
		s.size += INCREMENT;
	}
	*s.top++ = e;
	return true;

}
//出栈操作
bool Pop(stack &s, point &e)
{
	if(s.top == s.base)
		return false;
	e = *--s.top;
	return true;
}
//获得栈顶元素
bool GetTop(stack &s, point &e)
{
	if(s.top == s.base)
		return false;
	e = *(s.top-1);
	return true;

}

void CreateMaze(int maze[10][10])
{
	maze[0][0] = 0;maze[0][1] = 0;maze[0][2] = 0;maze[0][3] = 0;maze[0][4] = 0;maze[0][5] = 0;maze[0][6] = 0;maze[0][7] = 0;maze[0][8] = 0;maze[0][9] = 0;
	maze[1][0] = 0;maze[1][1] = 1;maze[1][2] = 1;maze[1][3] = 0;maze[1][4] = 1;maze[1][5] = 1;maze[1][6] = 1;maze[1][7] = 0;maze[1][8] = 1;maze[1][9] = 0;
	maze[2][0] = 0;maze[2][1] = 1;maze[2][2] = 1;maze[2][3] = 0;maze[2][4] = 1;maze[2][5] = 1;maze[2][6] = 1;maze[2][7] = 0;maze[2][8] = 1;maze[2][9] = 0;
	maze[3][0] = 0;maze[3][1] = 1;maze[3][2] = 1;maze[3][3] = 1;maze[3][4] = 1;maze[3][5] = 0;maze[3][6] = 0;maze[3][7] = 1;maze[3][8] = 1;maze[3][9] = 0;
	maze[4][0] = 0;maze[4][1] = 1;maze[4][2] = 0;maze[4][3] = 0;maze[4][4] = 0;maze[4][5] = 1;maze[4][6] = 1;maze[4][7] = 1;maze[4][8] = 1;maze[4][9] = 0;
	maze[5][0] = 0;maze[5][1] = 1;maze[5][2] = 1;maze[5][3] = 1;maze[5][4] = 0;maze[5][5] = 1;maze[5][6] = 1;maze[5][7] = 1;maze[5][8] = 1;maze[5][9] = 0;
    maze[6][0] = 0;maze[6][1] = 1;maze[6][2] = 0;maze[6][3] = 1;maze[6][4] = 1;maze[6][5] = 1;maze[6][6] = 0;maze[6][7] = 1;maze[6][8] = 1;maze[6][9] = 0;
    maze[7][0] = 0;maze[7][1] = 1;maze[7][2] = 0;maze[7][3] = 0;maze[7][4] = 0;maze[7][5] = 1;maze[7][6] = 0;maze[7][7] = 0;maze[7][8] = 1;maze[7][9] = 0;
	maze[8][0] = 0;maze[8][1] = 0;maze[8][2] = 1;maze[8][3] = 1;maze[8][4] = 1;maze[8][5] = 1;maze[8][6] = 1;maze[8][7] = 1;maze[8][8] = 1;maze[8][9] = 0;
	maze[9][0] = 0;maze[9][1] = 0;maze[9][2] = 0;maze[9][3] = 0;maze[9][4] = 0;maze[9][5] = 0;maze[9][6] = 0;maze[9][7] = 0;maze[9][8] = 0;maze[9][9] = 0;
	
}
//基本思想是在确定某点所在位置可行时，先朝该点的左移动一格作为新点，若行则把新点当成确定点，并且将新点入栈，若不行则按顺时针方向依次移动。
//若各个方向都不行，则让判断是否让栈顶元素出栈。把以经过的点都做标记。若到达终点点，则成功，若栈为空，则无出口
void MazePath(int maze[10][10], point startPoint, point endPoint)
{
	stack s;
	InitStack(s);
	int x = startPoint.x;
	int y = startPoint.y;
	maze[x][y] = 2;
	Push(s,startPoint);
	point temp;
	while(x != endPoint.x || y != endPoint.y)
	{
		if(maze[x][y+1] == 1)
		{
			y = y +1;
			// 做标记
			maze[x][y] = 2;
			temp.x = x;
			temp.y = y;
			Push(s, temp);
		}
		else if(maze[x+1][y] == 1)
		{
			x = x +1;
			maze[x][y] = 2;
			temp.x = x;
			temp.y = y;
			Push(s, temp);
		}
		else if(maze[x][y-1] == 1)
		{			
			y = y -1;
			maze[x][y] = 2;
			temp.x = x;
			temp.y = y;
			Push(s, temp);

		}
		else if(maze[x-1][y] == 1)
		{
			x = x -1;
			maze[x][y] = 2;
			temp.x = x;
			temp.y = y;
			Push(s, temp);

		}
		else
		{
			// 若该点四周都不通，则判断栈顶元素。
			if(GetTop(s, temp))
			{
				x = temp.x;
				y = temp.y;
			    //若栈顶元素四周也不通则将栈顶元素出栈并且考察下前一个可行元素
				if( maze[x][y+1] != 1 && maze[x+1][y] != 1 && maze[x][y-1] != 1 && maze[x-1][y] != 1)
				{
					Pop(s, temp);
					if(GetTop(s, temp))
			        {
						 x = temp.x;
						 y = temp.y;
					}
					else
					{
						cout << "无出口！！！！" <<endl;
				        return;

					}


				}
			}
			else
			{
				cout << "无出口！！！！" <<endl;
				return;
			}

		}
	}
	// 倒过来显示路径
	stack t;
	InitStack(t);
	while(Pop(s, temp))
	{
		Push(t,temp);
	}
	int i = 1;
	cout << "路径是：" << endl;
	while(Pop(t, temp))
	{
		cout << "第" << i++ << "步[" << temp.x << "," << temp.y <<"]";
	}
	cout << endl;
}

int _tmain(int argc, _TCHAR* argv[])
{
	int maze[10][10];
	CreateMaze(maze);
	cout << "迷宫图形是：" << endl;
	for( int i = 0; i < 10; i++)
	{
		for(int j = 0; j < 10; j++)
			cout << maze[i][j] << " ";
		cout << endl;
	}
	point start;
	start.x =1;
	start.y =1;
	point end;
	end.x =8;
	end.y =8;
	MazePath(maze, start, end);

	return 0;
}