hello.cpp

用递归算法和非递归算法实现的简单的“迷宫”程序

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

Maze::Maze()
{
   int Mark[ROW][COL]=
   {
	   {1,1,1,1,1,1},
	   {1,0,0,0,0,1},
	   {1,0,0,1,0,1},
	   {1,0,1,0,1,1},
	   {1,0,0,0,0,1},
	   {1,1,1,1,1,1}
   };
   for(int i=0;i<ROW;i++)
	   for(int j=0;j<COL;j++)
		   maze[i][j]=Mark[i][j];
}



//求解迷宫
int Maze::solve(int i, int j)
{
	int finish = 0;
	maze[i][j] = 8;
	
	if (i == (ROW-2)&& j == (COL-2))        //出口
		return 1; 
	
	//从maze[i][j]的周围八个方向探路

	if (!finish && maze[i][j+1] == 0)
		finish = solve(i, j+1);

	if (!finish && maze[i+1][j+1] == 0)
		finish = solve(i+1, j+1);

	if (!finish && maze[i+1][j] == 0)
		finish = solve(i+1, j);

	if (!finish && maze[i+1][j-1] == 0)
		finish = solve(i+1, j-1);

	if (!finish && maze[i][j-1] == 0)
		finish = solve(i, j-1);

	if (!finish && maze[i-1][j-1] ==0)
		finish = solve(i-1,j-1);

	if (!finish && maze[i-1][j] == 0)
		finish = solve(i-1, j);

	if (!finish && maze[i-1][j+1] ==0)
		finish = solve(i-1,j+1);
		
	return finish;
}

//非递归算法
int Maze::no_recurve(int i,int j)
{
	
	stack<int>Stack;//系统栈
	int finish=0;
	int mov=0;
	int g=i;
	int h=j;
	//用数组表示8个方向
	int Around[8][2]={{0,1},{1,0},{0,-1},{0,-1},{-1,0},{-1,0},{-1,1},{-1,1}};
	maze[i][j]=8;
	Stack.push(i);
	Stack.push(j);
	Stack.push(mov);
	while(!Stack.empty())
	{
		i  = Stack.top();
		j  = Stack.top();
		mov= Stack.top();
		Stack.pop();
		Stack.pop();
		Stack.pop();
		while(mov<=7)
		{
			i=g;
			j=h;

			g=i+Around[mov][0];//按逆时针方向走
			h=j+Around[mov][1];
			

		if(maze[g][h]==0)
		{
			if(g == (ROW-2) && h == (COL-2) && maze[ROW-2][COL-2]==0)  
			{
				maze[ROW-2][COL-2]=8;
				return 1;
			}
			maze[g][h]=8;
			Stack.push(i);
			Stack.push(j);
			Stack.push(mov);
			mov=0;
		}
		else
			mov=mov+1;//遇到墙则用mov标记出已走过的方向
		
		}
	}
	return finish;

}


//打印路径
void Maze::PrintPath()
{	

	for(int i=0;i<ROW;i++) 
	{
		for(int j=0;j<COL;j++) 
			cout<<maze[i][j]<<" ";
			cout<<endl;
	}

}