maze.cpp

构建用1

#include <iostream>
#include <cstdlib>
using namespace std;
const int maxsize=50;
#define m 3
#define n 2

struct elemtype
	{
		int i,j,v;
	};

template <class T>
class stack
{
public:
	stack(void);
	void push(const T& item);
	T pop(void);
	bool stackempty(void) const;
private:
	T stacklist[maxsize];
	int top;
};

template <class T>
stack<T>::stack(void) : top(-1)
{}
template <class T>
void stack<T>::push(const T& item)
{
	if(top==maxsize-1)
	{
		cerr<<"stack overflow"<<endl;
		exit(1);
	}
	top++;
	stacklist[top]=item;
}

template <class T>
T stack<T>::pop(void)
{
	T temp;
	if(top==-1)
	{
		cerr<<"stack is empty"<<endl;
		exit(1);
	}
	temp=stacklist[top];
	top--;
	return temp;
}

template <class T>
bool stack<T>::stackempty(void) const
{ return top==-1;}

int mazepath(int maze[][n+2],int mark[][n+2])
{
	int move[8][2]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};
	int g,h;
	mark[1][1]=1;
	stack<elemtype> s;
	elemtype stk,temp;
	stk.i=1;stk.j=1;stk.v=0;
	while(!s.stackempty()||stk.v!=7)
	{
		g=stk.i+move[stk.v][0];
		h=stk.j+move[stk.v][1];
		if(g==m&&h==n&&maze[m][n]==0)
		{
			s.push(stk);
			stk.i=m;stk.j=n;stk.v=0;
			s.push(stk);
			while(!s.stackempty()) 
			{
				temp=s.pop();
				cout<<"("<<temp.i<<","<<temp.j<<")"<<"--"<<temp.v<<endl;
				maze[temp.i][temp.j]=8;
			}
			return 1;
		}
		else if ((maze[g][h]==0)&&mark[g][h]==0)
		{
			mark[g][h]=1;
			s.push(stk);
			stk.i=g;stk.j=h;stk.v=0;
		}
		else
		{
			if(stk.v<7) stk.v=stk.v+1;
			else
			{
				while(stk.v==7&&!s.stackempty()) stk=s.pop();
				if(!s.stackempty()) stk=s.pop();
			}
		}
	}
	cout<<"can't solve"<<endl;
	return 0;
}
void main(void)
{
	int maze[m+2][n+2],mark[m+2][n+2];
	int i,j;
	cout<<"请输入迷宫:"<<endl;
	for(i=1;i<m+1;i++)
		for(j=1;j<n+1;j++)
			cin>>maze[i][j];
	
	for(i=0;i<m+2;i++)
		for(j=0;j<n+2;j++)
			mark[i][j]=0;
	
	for(i=0;i<n+2;i++)
	{maze[0][i]=1;maze[m+1][i]=1;}
	for(j=0;j<m+2;j++)
	{maze[j][0]=1;maze[j][n+1]=1;}
	cout<<endl<<"maze is :"<<endl;
		for(i=0;i<m+2;i++)
		{	for(j=0;j<n+2;j++)
				{cout<<maze[i][j]<<" ";}
			cout<<endl;
		}
		if(mazepath(maze,mark)) 
		{
			cout<<"ok"<<endl;
			cout<<endl<<"result is :"<<endl;
			for(i=0;i<m+2;i++)
			{	for(j=0;j<n+2;j++)
					{cout<<maze[i][j]<<" ";}
				cout<<endl;
			}
		}

}