#include <iostream>using namespace std;//定义四个方向#define EAST MAZE[x][y+1]#define WEST MAZE[x][y-1]#define SOUTH MAZE[x+1][y]#define NORTH MAZE[x-1][y]//起点(1,1),终点(8,10)const int startX=1;const int startY=1;const int ExitX=8;const int ExitY=10;//定义List结构保存坐标位置typedef struct List{ int x,y; struct List* next;}Node,*Link;//迷宫数组int MAZE[10][12]={ 1,1,1,1,1,1,1,1,1,1,1,1, 1,0,0,0,1,1,1,1,1,1,1,1, 1,1,1,0,1,1,0,0,0,0,1,1, 1,1,1,0,1,1,0,1,1,0,1,1, 1,1,1,0,0,0,0,1,1,0,1,1, 1,1,1,0,1,1,0,1,1,0,1,1, 1,1,1,0,1,1,0,1,1,0,1,1, 1,1,1,1,1,1,0,1,1,0,1,1, 1,1,0,0,0,0,0,0,1,0,0,1, 1,1,1,1,1,1,1,1,1,1,1,1,};Link Push_Stack(Link Stack,int,int);Link Pop_Stack(Link Stack,int*,int*);int CheckExit(int,int,int,int);int main(){ int i,j; Link path=NULL; int x=startX,y=startY; cout<<"迷宫如下:n"; for(i=0;i<10;i++) { for(j=0;j<12;j++) { if(MAZE[i][j]==1) cout<<"O "; else cout<<" "; } cout<<endl; } while(x<=ExitX && y<=ExitY) { //把当前位置标志为2,表示已走过的路径 MAZE[x][y]=2; //如果往NORTH方向可走,则向该方向走,并把新位置入栈,以下亦如此 if(NORTH==0) { x-=1; path=Push_Stack(path,x,y); } else if(SOUTH==0) { x+=1; path=Push_Stack(path,x,y); } else if(WEST==0) { y-=1; path=Push_Stack(path,x,y); } else if(EAST==0) { y+=1; path=Push_Stack(path,x,y); } //如果到达终点,则结束 else if(CheckExit(x,y,ExitX,ExitY)==1) break; //如果无路可走,则往回退一格 else { MAZE[x][y]=2; path=Pop_Stack(path,&x,&y); } } cout<<"nn老鼠走完的路径('*'): n"; for(i=0;i<10;i++) { for(j=0;j<12;j++) { if(MAZE[i][j]==1) cout<<"O "; else if(MAZE[i][j]==0) cout<<" "; else cout<<"* "; } cout<<endl; } cout<<"nn"; return 0;}//把位置坐标(x,y)入栈,以保存路径Link Push_Stack(Link Stack,int x,int y){ Link newNode=new Node; if(NULL==newNode) { cout<<"Memory allocate failed!n"; return 0; } newNode->x=x; newNode->y=y; newNode->next=Stack; Stack=newNode; return Stack;}//对不可行的位置进行出栈操作,x、y保存的是当前不可行位置的坐标Link Pop_Stack(Link Stack,int* x,int* y){ Link top; //非空时 if(NULL!=Stack) { top=Stack; Stack=Stack->next; *x=top->x; *y=top->y; delete top; return Stack; } else *x=-1; return Stack;}//对当前位置(x,y)进行判断是否已抵达终点(ex,ey)int CheckExit(int x,int y,int ex,int ey){ if(x==ex && y==ey) return 1; return 0;}