feidigui.cpp

迷宫问题是一个很古老的问题

#include <iostream.h>
#include <stdlib.h>
#define Maxsize 100

typedef struct 
{ int i,j,v;
} Stk;

class Stack
{public:
	Stack();
	void Push(Stk &a);
	Stk Pop();
	Stk GetPop();
	bool FullStack();
	bool EmptyStack();
	void ClearStack();
	void Output();

private:
	Stk stk[Maxsize];
	int top;
};

Stack::Stack()
{ top=-1;
}

void Stack::Push(Stk &a)
{if(top<Maxsize-1)
	{
		top++; stk[top]=a;
	}
else 
	{
		cout<<"The stack is full!"<<endl;exit(0);
	}
}

Stk Stack::Pop()
{if(top==-1)
	{cout<<"The stake is empty!"<<endl;
	exit(0);
	}
else return stk[top--];
}

Stk Stack::GetPop()
{if(top==-1)
	{cout<<"The stake is empty!"<<endl;
	exit(0);
	}
else return stk[top];
}

bool Stack::FullStack()
{return top==Maxsize-1;}

bool Stack::EmptyStack()
{return top==-1;}

void Stack::ClearStack()
{top=-1;}

void Stack::Output()
{int i;
 for(i=0;i<=top;i++)
	 cout<<"第 "<<i+1<<" 步  :"<<stk[i].i<<"  "<<stk[i].j<<" -->"<<stk[i].v<<endl;
}


void main()
{int maze[14][17]=							//初始化迷宫
	{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	 1,0,1,0,0,0,1,1,0,0,0,1,1,1,1,1,1,
	 1,1,0,0,0,1,1,0,1,1,1,0,0,1,1,1,1,
	 1,0,1,1,0,0,0,0,1,1,1,1,0,0,1,1,1,
	 1,1,1,0,1,1,1,1,0,1,1,0,1,1,0,0,1,
	 1,1,1,0,1,1,1,1,0,1,1,0,1,1,0,0,1,
	 1,1,1,0,1,0,0,1,0,1,1,1,1,1,1,1,1,
	 1,0,0,1,1,0,1,1,1,0,1,0,0,1,1,1,1,
	 1,0,1,1,1,1,0,0,1,1,1,1,1,1,1,1,1,
	 1,0,0,1,1,0,1,1,0,1,1,1,1,1,0,1,1,
	 1,1,1,0,0,0,1,1,0,1,1,0,0,0,0,0,1,
	 1,0,0,1,1,1,1,1,0,0,0,1,1,1,1,0,1,
	 1,0,1,0,0,1,1,1,1,1,0,1,1,1,1,0,1,
	 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
	};
 int move[9][3]=
	{0,0,0,
	 0,0,1,
	 0,1,1,
	 0,1,0,
	 0,1,-1,
	 0,0,-1,
	 0,-1,-1,
	 0,-1,0,
	 0,-1,1,
	};
 static int mark[14][17];
 Stack stack;
 Stk stk;
 mark[1][1]=1;
 int g,h;
 stk.i=1; stk.j=1;stk.v=1;
 while(!stack.EmptyStack()||stk.v!=8)		
	{
	 g=stk.i+move[stk.v][1];
	 h=stk.j+move[stk.v][2];
	 if(g==12&&h==15)				//如果到达终点
		{stack.Push(stk);
		stk.i=12;stk.j=15;stk.v=0;
		stack.Push(stk);
		while(!stack.EmptyStack())
			{stk=stack.Pop();
			 cout<<"i: "<<stk.i<<"  j:"<<stk.j<<"  next step:"<<stk.v<<endl;
			 maze[stk.i][stk.j]=8;
			}
         break;
		}
	else 
		if(maze[g][h]==0&&mark[g][h]==0)		//如果可以走而且没有走过
		{ 
		mark[g][h]=1;
		stack.Push(stk);
		stk.i=g;stk.j=h;stk.v=0;
		}
	else 
		{ 
		  if(stk.v<8) stk.v=stk.v+1;
		  else
			{
			  while(stk.v==8&&!stack.EmptyStack())	//如果八个方向都试探完，则逐个退栈
				stk=stack.Pop();
			if(stack.EmptyStack()) break;
			}
		}
	}												//while循环结束  
 
 for(int i1=0;i1<14;i1++)						//输出最终路径
	{for(int j1=0;j1<17;j1++)
	   cout<<maze[i1][j1]<<' ';
	 cout<<endl;
	}


}