自定义栈实现迷宫求解(C++版)

                                                           迷宫求解

一：迷宫求解是一个锻炼我们的算法求解能力的问题，它的实现方法有很多；今天我们就介绍其中的用栈求解的方法。

二：什么是栈：

      大家应该都有往袋子里装东西的经历，在往袋子里装满东西之后，当我们去取的时候，总是先从最后放进去的东西的地方去取。也就是后进先出(FILO)。虽然栈的单向性用起来会没有链表那样可以在任意位置对数据进行操作，但是正因为如此栈也带来了很大的方便。

三：迷宫求解

现在我们要在下面的迷宫寻找一条可行的路径

 

1 1 1 1 1 1 1 1 1 1

1 0 0 1 1 0 0 0 0 1

1 0 0 0 1 0 1 0 0 1

1 0 1 0 0 0 1 1 0 1

1 0 1 0 0 0 1 1 1 1

1 0 1 1 1 0 1 1 1 1

1 0 1 1 1 0 1 1 1 1

1 1 1 1 1 0 0 0 1 1

1 1 1 1 1 1 1 0 0 1

1 1 1 1 1 1 1 1 1 1

首先我们需要在程序中表示上面的迷宫，该问题可以用数组实现

1：栈的定义

 

/************************************************************************/
/*自定义栈                                                                         */
/*通过自定义的简单栈以满足迷宫求解                */
/*功能：push() 将元素加入栈中                                  */
/*               pop() 退栈；topValue() 获得栈顶元素        */
/*				  clear() 清除栈 length() 获得栈中元素个数*/
/************************************************************************/
#include <stack>
#include <iostream>
using namespace std;

template<typename Elem> class PathStack: public stack<Elem>
{
private:
	int size;
	int top;
	Elem* listArray;
public:
	PathStack(int sz = DefaultListSize){
		size = sz;
		top = 0;
		listArray = new Elem[sz];
	}
	~PathStack(){ delete []listArray; }
	void clear(){ top = 0; }
	/****向栈中加入元素****/
	bool push(const Elem& item);
	/***********退栈**********/
	Elem pop();
	/********获得栈顶元素*******/
	Elem topValue() const;
	int length() const { return top; }
};

template<typename Elem>
bool PathStack<typename Elem>::push(const Elem& item){
	if(top == size) return false;
	listArray[top++] = item;
	return true;
}

template<typename Elem>
Elem PathStack<typename Elem>::pop(){
	Elem it;
	if(top == 0) return it;
	it = listArray[--top]; 
	return it;
}

template<typename Elem>
Elem PathStack<typename Elem>::topValue() const{
	Elem it;
	if(top == 0) return it;
	it = listArray[top - 1];
	return it;
}

 

 2：如何实现路径的寻找

     1：设定寻找的方向，可以使用一个判断语句；判断起始位置周围哪个地方有路就将该位置的坐标加入到栈中，并将该位置标记(将改位置值改为2,既将走过的位置标记为2)

     2：判断该位置周围是否还有路，若没有则退栈即退回到上一个位置；并将该位置做下另一个标记(将该位置值改为3,既将退栈位置值用3标记)

     3：重复1,2步骤直到达到出口

     路径寻找的类：

 

//迷宫求解的方法类
//功能：通过findPath() 方法实现对路径的查找
//              通过printPath()方法将路径打印出来
#include "PathStack.h"
#include <iostream>
using namespace std;

class MazeSolveMethod
{
private:
	static int maze[10][10];//存放迷宫数据
	PathStack<int> pathStack;//定义栈
public:
	MazeSolveMethod():pathStack(100){
	}
	~MazeSolveMethod(){ }
	void findPath(int startX,int startY);
	void printPath() const;
};

int MazeSolveMethod::maze[10][10] = {
	{1,1,1,1,1,1,1,1,1,1},
	{1,0,0,1,1,0,0,0,0,1},
	{1,0,0,0,1,0,1,0,0,1},
	{1,0,1,0,0,0,1,1,0,1},
	{1,0,1,0,0,0,1,1,1,1},
	{1,0,1,1,1,0,1,1,1,1},
	{1,0,1,1,1,0,1,1,1,1},
	{1,1,1,1,1,0,0,0,1,1},
	{1,1,1,1,1,1,1,0,0,1},
	{1,1,1,1,1,1,1,1,1,1},
};

void MazeSolveMethod::findPath(int startX,int startY){
	int x = startX;
	int y = startY;
	pathStack.push(x);
	pathStack.push(y);
	maze[x][y] = 2;
	cout<<"进入方法！"<<endl;
	while(true){
		if(maze[x-1][y] == 0){
			pathStack.push(--x);
			pathStack.push(y);
			maze[x][y] = 2;
		}else if(maze[x][y-1] == 0){
			pathStack.push(x);
			pathStack.push(--y);
			maze[x][y] = 2;
		}else if(maze[x][y+1] == 0){
			pathStack.push(x);
			pathStack.push(++y);
			maze[x][y] = 2;
		}else if(maze[x+1][y] == 0){
			pathStack.push(++x);
			pathStack.push(y);
			maze[x][y] = 2;
		}
		if(maze[x-1][y] != 0 && maze[x][y+1] != 0 && maze[x+1][y] != 0 && maze[x][y-1] != 0){				
			if(x >= 8 && y >= 8){
				break;
			}else{
				maze[x][y] = 3;
				y = pathStack.pop();
				x = pathStack.pop();
			}
			y = pathStack.topValue();
			int temp = pathStack.pop();
			x = pathStack.topValue();
			pathStack.push(temp);
		}
	}
}

void MazeSolveMethod::printPath() const{
	cout<<"printPath"<<endl;
	for(int i=0; i<10; i++){
		for(int j=0; j<10; j++){
			if(maze[i][j] == 2)
				cout<<'*'<<"  ";
			else if(maze[i][j] == 3)
				cout<<0<<"  ";
			else
				cout<<1<<"  ";
		}
		cout<<endl;
	}
}

   主函数类

 

/************************************************************************/
/*迷宫求解----栈方法实现*/
//功能：通过对栈实现迷宫算法求解
//Author：Andrew
//Date   ：2012-10-20
/************************************************************************/
#include "MazeSolveMethod.h"
#include <iostream>
using std::cout;
using std::endl;

int main(){

	MazeSolveMethod solve;
	solve.findPath(1,1);
	solve.printPath();
	system("pause");
	return 0;
}

 将上面的代码运行后结果截图如下：

 其中* 为路径