走迷宫程序C++

走迷宫程序（C++小程序）以数组标记，得出正确路线

#include

#define N 5

int m[N][N] = {
	{00111}
	{01001}
	{11110}
	{01000}
	{11111}
};

//标志数组
bool flag[N][N];

typedef struct position
{
	int row;
	int col;
}POSITION;

typedef struct node
{
	POSITION pos;
	struct node* pNext;
}NODE*PNODE;

class Stack
{
private:
	PNODE pBottom;
	PNODE pTop;
	
public:
	Stack（）
	{
		pBottom = pTop = new NODE;
		pBottom->pNext = NULL;
	}
	
	void Push（POSITION pos）
	{
		PNODE pNew = new NODE;
		pNew->pos = pos;
		pNew->pNext = pTop;
		
		pTop = pNew;
	}
	
	bool IsNULL（）
	{
		if（pBottom == pTop）
			return true;
		else
			return false;
	}
	
	POSITION Pop（）
	{
		POSITION pos = pTop->pos;
		
		PNODE p = pTop;
		pTop = pTop->pNext;
		delete p;
		
		return pos;
	}
	
	void Clear（）
	{
		while（!IsNULL（））
		{
			Pop（）;
		}
	}
	
	void Print（）
	{
		PNODE p = pTop;
		
		while（p != pBottom）
		{
			cout<pos.row<<“ “<pos.col<			p = p->pNext;
		}
	}
	
	//返回栈顶元素
	POSITION GetTop（）
	{
		return pTop->pos;
	}
	
	~Stack（）
	{
		Clear（）;
		delete pBottom;
	}
};

void InitFlag（）
{
	for（int i=0;i	{
		for（int j=0;j		{
			flag[i][j] = false;
		}
	}
}

void Migong（POSITION pos_beginPOSITION pos_end）
{
	Stack st;//栈
	POSITION pos_cur;//当前位置
	POSITION pos_new;//新位置
	bool IsFind;//判断是否找到合法新位置
	
	InitFlag（）;//初始化标记数组
	
	st.Push（pos_begin）;//走到出发点
	flag[pos_begin.row][pos_begin.col] = true;//设置已经走过标志
	
	while（!st.IsNULL（） 
		&& 
		（st.GetTop（）.row != pos_end.row || st.GetTop（）.col != pos_end.col））
	{	
		pos_cur = st.GetTop（）;//获得当前位置
		
		IsFind = false;
		
		for（int i=0;i<4;i++）//查找4个方向
		{
			if（i==0）//0 方向
			{
				pos_new.row = pos_cur.row;
				pos_new.col = pos_cur.col-1;
				
			}
			else if（i == 1）//1 方向
			{
				pos_new.row = pos_cur.row+1;
				pos_new.col = pos_cur.col;
			}
			else if（i == 2）
			{
				pos_new.row = pos_cur.row;
				pos_new.col = pos_cur.col+1;
			}
			else
			{
				pos_new.row = pos_cur.row-1;
				pos_new.col = pos_cur.col;
			}
			
			
			if（（pos_new.row>=0 && pos_new.row<=4 &&pos_new.col>=0 && pos_new.col<=4）//不越界
				&&
				flag[pos_new.row][pos_new.col] == false//没走过
				&&
				m[pos_new.row][pos_new.col] == 1//是通路
				）
			{
				IsFind = true;//设置找到合法新位置的标志
				break;
			}
		}
		
		if（IsFind）
		{
			st.Push（pos_new）;
			flag[pos_new.row][pos_new.col] = true;
		}
		else
		{
			st.Pop（）;
		}
	}

	if（st.IsNULL（））//未找到出路
	{
		cout<<“迷宫是死的，没有出路!!!“<	}
	else
	{
		cout<<“找到一条出路：“<		st.Print（）;
	}
}

void main（）
{
	POSITION pos_begin;
	POSITION pos_end;

	pos_begin.row = 4;
	pos_begin.col = 0;

	pos_end.row = 0;
	pos_end.col = 4;


	Migong（pos_beginpos_end）;

}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       2923  2005-01-04 13:07  maze.cpp

----------- ---------  ---------- -----  ----

                 2923                    1