逃出迷宫完整算法C++

本文主要是介绍逃出迷宫完整算法C++，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

迷宫图案，白色代表通道，黑色代表墙。
 迷宫入口坐标(1,1),出口坐标(8,8)
  0 1 2 3 4 5 6 7 8 9
  0■■■■■■■■■■
  1■□□■□□□■□■
  2■□□■□□□■□■
  3■□□□□■■□□■
  4■□■■■□□□□■
  5■□□□■□□□□■
  6■□■□□□■□□■
  7■□■■■□■■□■
  8■■□□□□□□□■
  9■■■■■■■■■■

 

程序源代码(VC++ 6.0下编译通过)

#include<iostream>  using namespace std;const int SIZE_X = 10;
const int SIZE_Y = 10;//data structstruct mPoint
{int x;int y;bool can_move_to;mPoint(int rx = 0, int ry = 0, bool rcan_move_to = false){x= rx;y = ry;can_move_to = rcan_move_to;next = NULL;}mPoint* next;
};//function declaration
class mStack
{
public:mStack();//constructorint push(mPoint point);mPoint pop();int getLength();mPoint getTop();void printStack();
private:mPoint *base;//base pointermPoint *top; //top pointerint length; //length of stack
};int main()
{mPoint mpArray[SIZE_X][SIZE_Y];bool initArray[SIZE_X][SIZE_Y]={{ false, false, false, false, false, false, false, false, false, false },{ false, true, true, false, true, true, true, false, true, false },{ false, true, true, false, true, true, true, false, true, false },{ false, true, true, true, true, false, false, true, true, false },{ false, true, false, false, false, true, true, true, true, false },{ false, true, true, true, false, true, true, true, true, false },{ false, true, false, true, true, true, false, true, true, false },{ false, true, false, false, false, true, false, false, true, false },{ false, false, true, true, true, true, true, true, true, false },{ false, false, false, false, false, false, false, false, false, false }};//迷宫矩阵 for(int i = 0; i<SIZE_X;i++){for(int j=0; j<SIZE_Y;j++){mpArray[i][j].x = i;mpArray[i][j].y = j;mpArray[i][j].can_move_to = initArray[i][j];}} mPoint startup(1,1,true);//entrymPoint endp(8,8,true);//exitmStack mpath;mpath.push(startup);mPoint mp = startup;while(true){if(mp.x == endp.x && mp.y == endp.y){break;}if(mpArray[mp.x+1][mp.y].can_move_to){mpArray[mp.x+1][mp.y].can_move_to=false;mpath.push(mPoint(mp.x+1,mp.y));mp = mpArray[mp.x+1][mp.y];continue;}if(mpArray[mp.x-1][mp.y].can_move_to){mpArray[mp.x-1][mp.y].can_move_to=false;mpath.push(mPoint(mp.x-1,mp.y));mp = mpArray[mp.x-1][mp.y];continue;}if(mpArray[mp.x][mp.y+1].can_move_to){mpArray[mp.x][mp.y+1].can_move_to=false;mpath.push(mPoint(mp.x,mp.y+1));mp = mpArray[mp.x][mp.y+1];continue;}if(mpArray[mp.x][mp.y-1].can_move_to){mpArray[mp.x][mp.y-1].can_move_to=false;mpath.push(mPoint(mp.x,mp.y-1));mp = mpArray[mp.x][mp.y-1];continue;}if(0 == mpath.getLength()){cout<<"No path"<<endl;return -1;}mpath.pop();mp = mpath.getTop();}cout<<"Path:"<<endl;mpath.printStack();getchar();return 0;}
mStack::mStack()
{length = 0;base = NULL;top = NULL;
}
int mStack::push(mPoint point)
{mPoint *mpNode = new mPoint();*mpNode = point;if (length == 0)top = base = mpNode;else{top->next = mpNode;top = mpNode;}return ++length;
}
mPoint mStack::getTop()
{return *top;
}
mPoint mStack::pop()
{if (length <= 0)return NULL;mPoint retPoint = *top;top = base;while (top->next != NULL){if (top->next->next == NULL){delete(top->next);top->next = NULL;break;}top = top->next;}if (length == 1){delete(base);base = top = NULL;}length--;return retPoint;
}int mStack::getLength()
{return length;
}
void mStack::printStack()
{mPoint *p = base;while (p != NULL){cout << "(" << p->x << "," << p->y << ")" << endl;p = p->next;}}

本程序堆栈用单向动态链表实现，当然可以用其他数据结构，比如双向链表。

程序输出结果：

Path:
(1,1)
(2,1)
(3,1)
(4,1)
(5,1)
(5,2)
(5,3)
(6,3)
(6,4)
(6,5)
(7,5)
(8,5)
(8,6)
(8,7)
(8,8)

这篇关于逃出迷宫完整算法C++的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---