mazeddddd.cpp

一个关于迷宫的程序

#include <iostream.h>
#include <stdlib.h>
#include <string.h>

#define Edge 10
#define PLUS 5
#define STA_SIZE 100
#define Startx 1
#define Starty 1

typedef struct Datastore{
	int x, y, d, lsx, lsy;
	bool nl;
} Datastore, *Link; // 储存走过的路

Datastore InitDatastore (Datastore &d) {
	d.x = d.lsx = Startx;
	d.y = d.lsy = Starty;
	d.d = 4;
	d.nl = false;
	return d;
}

typedef struct {
	Link base;
	Link top;
	int stacksize;
	// count 记录栈内实时的数据个数
	int count;
	// 用array数组来记录迷宫内路径是否被访问过用来防止走回头路
	bool array[Edge*Edge];
} SqStack; // 栈

bool Push(SqStack &S, Datastore &e)
{
	if(S.top - S.base >= S.stacksize) {
		S.base = (Link) realloc (S.base, (S.stacksize + PLUS) * sizeof (Datastore));
		if (!S.base) return false;
		S.top = S.base + S.stacksize;
		S.stacksize += PLUS;
	}
	*(++S.top) = e;
	S.count++;
	return true;
} // Push函数

bool Pop(SqStack &S, Datastore &e) {
	if(S.top == S.base) return false;
	e = *(--S.top);
	S.count--;
	return true;
} // Pop函数

bool InitStack (SqStack &S) {
	S.base = (Link) malloc (STA_SIZE * sizeof(Datastore));
	if(!S.base) return false;
	S.top = S.base;
	S.stacksize = STA_SIZE;
	S.count = 0;
	for(int i = 0; i<Edge*Edge; i++ )
		S.array[i] = false;
	return true;
} // 构造个新栈S

bool DestroyStack (SqStack &S) {
	if(!S.base) return false;
	for (int i = 0; i<STA_SIZE; i++)
		free(S.top);
	return true;
}

bool NextPos (int a[], SqStack &S, Datastore &e) {
	// case中要判断,此次的位置是否为原来来的位置
	// 只要还有方向未试探,则继续试探,直到方向d=0为止
	for(; e.d>=0; )
	{
		switch(e.d)
		{
		case 4:
			// right 
			// 方向减1,消除走不通的方向
			e.d--;
			// 如果下一步为路(0)或出口(-1),且如果为路,不是当前位置的前一位置,那么确认并记录下当前试探位置为后一位置
			// 如果条件不满足,即是墙,则判断下一方向
			if(a[S.top->x * Edge + (S.top->y + 1)] <= 0 && S.top->lsy != (e.y + 1) && S.array[S.top->x * Edge + (S.top->y + 1)] == false)
			{
				e.y++;
				S.array[S.top->x * Edge + (S.top->y + 1)] = true;
				return true;
			}
			break;
		case 3:
			// down
			e.d--;
			if(a[(S.top->x + 1) * Edge + S.top->y] <= 0 && S.top->lsx != (e.x + 1) && S.array[(S.top->x + 1) * Edge + S.top->y] == false)
			{
				e.x++;
				S.array[(S.top->x + 1) * Edge + S.top->y] = true;
				return true;
			}
			break;
		case 2:
			// left
			e.d--;
			if(a[S.top->x * Edge + (S.top->y - 1)] <= 0 && S.top->lsy != (e.y - 1) && S.array[S.top->x * Edge + (S.top->y - 1)] == false)
			{
				e.y--;
				S.array[S.top->x * Edge + (S.top->y - 1)] = true;
				return true;
			}
			break;
		case 1:
			// up
			e.d--;
			if(a[(S.top->x - 1) * Edge + S.top->y] <= 0 && S.top->lsx != (e.x - 1) && S.array[(S.top->x - 1) * Edge + S.top->y] == false)
			{
				e.x--;
				S.array[(S.top->x - 1) * Edge + S.top->y] = true;
				return true;
			}
			break;
			/*
			// 如果4个方向都判断为失败,那么当前路段迷宫到尽头,并把nl赋为真,即表明路到了尽头
			else 
			{
				S.top->nl = true;
				// cout << "当前路到尽头..." << endl;
				return false;
			}b
			/*/
			//*
		default:
			S.top->nl = true;
			return false;
			//*/
		}
	}
	return false;
}

void Patch (int a[], Datastore &d, SqStack &S) {
	// a[d.x*Edge + d.y];
	while(a[S.top->x*Edge + S.top->y] != -1)
	{
		if(NextPos(a, S, d))
		{
			Push(S, d);
			// 前一个的方向是S.top的方向
			(S.top-1)->d = S.top->d;
			// 当前top指的点还未分配方向
			S.top->d = d.d = 4;
			// 把当前top的x和y给下一个坐标的记录区
			d.lsx = S.top->x;
			d.lsy = S.top->y;
		}
		else
		{
			while(S.top->nl)
			{
				Datastore td;
				// 如果四个方向都失败,nl为true,出栈
				Pop(S, td);
				d = *S.top;
				d.lsx = d.x;
				d.lsy = d.y;
				/*
				// 出栈后,top指针退一格,且把现在top指针的方向d给将要试探下步的临时变量d
				d.d = S.top->d;
				// 出栈后,把后来要处理的d的坐标换成当前top指针的坐标
				// 把当前位置的坐标给下个处理d的记忆坐标
				d.lsx = d.x = S.top->x;
				d.lsy = d.y = S.top->y;
				//*/
			}
			if(S.top->x == Startx && S.top->y == Starty)
			{
				// 如果出栈到当前位置为起始位置,那么迷宫无解
				cout << "error! 迷宫无解" << endl;
				return;
			}
		}
	}
	//a[d.x*Edge + d.y] = 1;
}

// 判断方向连接
//*
void Jugedir (Link top, char dir[])
{
	switch(top->d)
	{
	case 3:
		strcpy(dir,"Right<向右>");
		break;
	case 2:
		strcpy(dir,"Down<向下>");
		break;
	case 1:
		strcpy(dir,"Left<向左>");
		break;
	case 0:
		strcpy(dir,"Up<向上>");
	}
}
//*/

void PrintMaze (SqStack &S) {
	SqStack Sq;
	InitStack(Sq);
	// 倒序入栈
	for(;S.top != S.base;S.top--)
	{
		*(++Sq.top) = *S.top;
	}
	Sq.count = 1;// 做表格用
	// 用函数中建立的新栈来顺序输出结果
	for(;Sq.top != Sq.base;Sq.top--,Sq.count++)
	{
		char dir[10];
		Jugedir(Sq.top, dir);
		cout << "(" << Sq.top->x << "," << Sq.top->y << "," << dir << ") " << "\t";
		if(Sq.count%2 == 0)
			cout << endl;
	}
	cout << endl;
	cout << "走过" << S.count << "步..." << endl;
}
	

void main()
{
	int maze[Edge][Edge] = {
		//	 1	2  3  4  5  6  7  8
		{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
		{ 1, 0, 1, 0, 1, 0, 1, 1, 1, 1},	// 1
		{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 1},	// 2
		{ 1, 1, 1, 1, 1, 1, 0, 1, 0, 1},	// 3
		{ 1, 0, 0, 0, 0, 0, 0, 1, 0, 1},	// 4
		{ 1, 0, 1, 0, 1, 1, 1, 1, 0, 1},	// 5
		{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 1},	// 6
		{ 1, 0, 1, 1, 1, 1, 1, 1, 1, 1},	// 7
		{ 1, 0, 0, 0, 0, 0, 0, 0,-1, 1},	// 8
		{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
	};
//*
	for(int i=0; i<Edge; i++)
		for(int j=0; j<Edge; j++)
		{
			if (j==0) cout << endl;
			cout << maze[i][j] << "  ";
		}
	cout << endl;
//*/
	Datastore d;
	InitDatastore(d);
	SqStack S;
	InitStack(S);
	Push(S, d);
	Patch(maze[0], d, S);
	PrintMaze(S);
	// DestroyStack(S);
}