迷宫求解
一:迷宫求解是一个锻炼我们的算法求解能力的问题,它的实现方法有很多;今天我们就介绍其中的用栈求解的方法。
二:什么是栈:
大家应该都有往袋子里装东西的经历,在往袋子里装满东西之后,当我们去取的时候,总是先从最后放进去的东西的地方去取。也就是后进先出(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;
}
将上面的代码运行后结果截图如下:
其中* 为路径
- 大小: 18.8 KB
分享到:
相关推荐
主要介绍了C++ 自定义栈实现迷宫求解的相关资料,需要的朋友可以参考下
迷宫求解 C++ 迷宫求解 C++ 迷宫求解 C++ 迷宫求解 C++ 迷宫求解 C++ 迷宫求解 C++ 迷宫求解 C++ 迷宫求解 C++
c语言:用栈实现迷宫求解 用栈实现迷宫求解c语言描述 很好的东西
利用栈实现迷宫问题的的求解,附详细图文,代码。。
数据结构 迷宫求解 C++ 数据结构 迷宫求解 C++ 数据结构 迷宫求解 C++
《数据结构》上机实验报告—利用栈实现迷宫求解.pdf
熟练使用栈实现迷宫的求解,看过就知道了,呵呵
数据结构试验实验一题目3——利用栈结构实现迷宫求解问题。
用栈实现求解……迷宫由系统随机产生……路径由箭头标明……
这是一个数据结构中用栈实现迷宫求解的例子 经实现可以运行
用栈辅助实现迷宫问题的求解,通过随机数发生器产生迷宫图,程序显示求解步骤
迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解迷宫求解...
用栈实现的迷宫可行路径求解,原是数据结构的练习题
数据结构课程设计 迷宫求解C++语言描述 这是一个数据结构的课程设计,我选择了迷宫求解 这个题目,使用C++语言才描述,经测试无误,测试环境:Windows 7 x64 旗舰版,Visual Studio 2010 旗舰版
为了实现上述操作,以栈为存储结构。 本程序包含三个模块: (1) 主程序模块:实现人机交互。 (2) 迷宫生产模块:随机产生一个12×12的迷宫。 (3) 路径查找模块:实现通路的查找。 (4) 求解迷宫中一条通路的伪...
栈在迷宫求解问题中的应用.pdf栈在迷宫求解问题中的应用.pdf栈在迷宫求解问题中的应用.pdf栈在迷宫求解问题中的应用.pdf栈在迷宫求解问题中的应用.pdf
题目如下:利用栈结构实现迷宫求解问题。迷宫求解问题如下: 心理学家把一只老鼠从一个无顶盖的大盒子的入口赶进迷宫,迷宫中设置很多隔壁,对前进方向形成了多处障碍,心理学家在迷宫的唯一出口放置了一块奶酪,...
基于栈的迷宫求解,数据结构课程作业(C语言),源代码及注释。
c++实现迷宫求解。大一计算机科学与技课程设计。在设定的迷宫中找到出路。