C++迷宫求解(基于栈)(动态寻找出口并显示路线)

1、/C+实现动态迷宫求解，基于类和栈结构；/迷宫大小、构造以及入口出口位置可人为设定；/动态显示寻找出口的过程，最终显示路线。#include<iostream>#include<cstdlib>#include <windows.h>using namespace std;#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define N 12 /迷宫规模/int mazeNN=/3,3,3,3,3,3,3,3,3,3,/3,0,0,3,0,0,0,3,0,3,/3,0,0,3,0,0,0,3,0,3,

2、/3,0,0,0,0,3,3,0,0,3,/3,0,3,3,3,0,0,0,0,3,/3,0,0,0,3,0,0,0,0,3,/3,0,3,0,0,0,3,0,0,3,/3,0,3,3,3,0,3,3,0,3,/3,3,0,0,0,0,3,0,0,3,/3,3,3,3,3,3,3,3,3,3/;int mazeNN=3,3,3,3,3,3,3,3,3,3,3,3,3,0,0,3,0,0,0,3,0,0,0,3,3,0,0,3,0,0,0,3,0,3,0,3,3,0,0,0,0,3,3,0,0,3,0,3,3,0,3,3,3,0,0,3,3,0,0,3,3,0,0,0,3,0,0,0,0,0,0

3、,3,3,0,3,0,0,0,3,0,3,3,3,3,3,0,3,3,3,0,3,0,0,0,0,3,3,3,0,0,0,0,3,0,3,0,0,3,3,3,0,3,3,0,3,3,0,3,0,3,3,3,0,0,0,0,3,0,0,0,0,3,3,3,3,3,3,3,3,3,3,3,3,3,;HANDLE hOut;COORD pos;class Pospublic:Pos(int x,int y)xpos=x;ypos=y;Pos()xpos=0;ypos=0;int xpos;int ypos;bool operator = (Pos pos1,Pos pos2)if(pos1.xpos

4、=pos2.xpos&&pos1.ypos=pos2.ypos) return true;else return false;Pos start(1,1),end(9,8); /入口及出口位置class Blockpublic:Block()ord=0;di=1;int ord;Pos seat;int di;class Stackpublic:Stack();Stack()delete base;void push(Block);void pop(Block&);friend int Mazepath(Pos,Pos);friend void printsteps(S

5、tack);friend void printonestep(Stack);private:Block *top;Block *base;int stacksize;Stack:Stack()base=new BlockSTACK_INIT_SIZE;top=base;stacksize=STACK_INIT_SIZE;void Stack:push(Block e)if(top-base>=stacksize)Block *newbase=new Blockstacksize+STACKINCREMENT;for(int i=0;i<stacksize;i+)newbasei=b

6、asei;delete base;base=newbase;top=base+stacksize;stacksize+=STACKINCREMENT;*top=e;top+;void Stack:pop(Block &e)if(top=base) return;e=*-top;int pass(Pos cur)if(mazecur.xposcur.ypos=0) return 1;else return 0;void footprint(Pos cur)mazecur.xposcur.ypos=1;Pos nextpos(Pos cur,int d)Pos pos1;switch(d)

7、case 1:pos1.xpos=cur.xpos;pos1.ypos=cur.ypos+1;return pos1;case 2:pos1.xpos=cur.xpos+1;pos1.ypos=cur.ypos;return pos1;case 3:pos1.xpos=cur.xpos;pos1.ypos=cur.ypos-1;return pos1;case 4:pos1.xpos=cur.xpos-1;pos1.ypos=cur.ypos;return pos1;default:break;void markprint(Pos cur)mazecur.xposcur.ypos=2;void

8、 printsteps(Stack s)Block *p=s.base;while(p+1)!=s.top)if(p->seat.xpos=(p+1)->seat.xpos&&p->seat.ypos=(p+1)->seat.ypos-1) mazep->seat.xposp->seat.ypos=4;else if(p->seat.xpos=(p+1)->seat.xpos-1)&&p->seat.ypos=(p+1)->seat.ypos) mazep->seat.xposp->seat

9、.ypos=5;else if(p->seat.xpos=(p+1)->seat.xpos&&p->seat.ypos=(p+1)->seat.ypos+1) mazep->seat.xposp->seat.ypos=6;else if(p->seat.xpos=(p+1)->seat.xpos+1)&&p->seat.ypos=(p+1)->seat.ypos) mazep->seat.xposp->seat.ypos=7;p+;for(int i=0;i<N;i+)for(int

10、j=0;j<N;j+)if(mazeij=3) cout<<(char)91<<(char)93;else if(mazeij=4) cout<<(char)26<<' 'else if(mazeij=5) cout<<(char)25<<' 'else if(mazeij=6) cout<<(char)27<<' 'else if(mazeij=7) cout<<(char)24<<' 'else if(

11、i=end.xpos&&j=end.ypos) cout<<"$"else cout<<" "cout<<endl;cout<<endl;p=s.base;int ent=0;while(p+1)!=s.top)cout<<'('<<p->seat.xpos<<','<<p->seat.ypos<<") -> "p+;ent+;if(ent=4)ent=0;cou

12、t<<endl;cout<<'('<<p->seat.xpos<<','<<p->seat.ypos<<')'<<endl;void printonestep(Stack s)pos= (s.top-1)->seat.ypos*2,(s.top-1)->seat.xpos; /* 光标的起始位 SetConsoleCursorPosition(hOut, pos); cout<<(char)17<<(char)16;

13、_sleep(200);pos= (s.top-1)->seat.ypos*2,(s.top-1)->seat.xpos;if(!(s.top-1)->seat.xpos=end.xpos&&(s.top-1)->seat.ypos=end.ypos) SetConsoleCursorPosition(hOut, pos); cout<<" "int Mazepath(Pos start,Pos end)Stack s;Pos curpos=start;Block e;int curstep=1;int l=1;doif(

14、pass(curpos)footprint(curpos);e.ord=curstep;e.seat=curpos;e.di=1;s.push(e);printonestep(s);if(curpos=end) pos= 0,N; SetConsoleCursorPosition(hOut, pos);cout<<endl<<"Find the path!"<<endl<<endl; printsteps(s);return 1;curpos=nextpos(curpos,1);curstep+;if(l=1)s.base-&

15、gt;ord=1;s.base->seat.xpos=start.xpos;s.base->seat.ypos=start.ypos;s.base->di=1;l=0;elseif(s.top!=s.base)s.pop(e);while(e.di=4&&s.top!=s.base)markprint(e.seat);printonestep(s);s.pop(e);if(e.di<4)e.di+;s.push(e);curpos=nextpos(e.seat,e.di);while(s.top!=s.base);return 0;int main()hOut = GetStdHandle(STD_OUTPUT_HANDLE); for(int i=0;i<N;i+)for(int j=0;j<N;j+)if(mazeij=3) cout<<(char)91<<(char)93;else if(i=end.xpos&&j=end.ypos) cout<<"$&