c语言迷宫算法（c++迷宫求解）

本文以实例形式描述了C++实现迷宫算法。本例中的迷宫是一个矩形区域，它有一个入口和一个出口。在迷宫的内部包含不能穿越的墙或障碍。障碍物沿着行和列放置，它们与迷宫的矩形边界平行。迷宫的入口在左上角，出口在右下角

本实例迷宫算法的功能主要有：

1.自动生成10*10迷宫图

2.判断是否有迷宫出口，并且画出路线图

具体实现代码如下：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 # include <iostream> # include <list> # include <sys/timeb.h> # include <time.h> # include <windows.h> using namespace std; bool Makework(int Sam[10][10]);//判断迷宫是否有出口 void main() { struct _timeb timebuffer; _ftime(&timebuffer); unsigned short int tem=timebuffer.millitm; unsigned short int a=0; srand(tem); int quit=1; int Mou[10][10]; while(quit==1) { for(int i=0;i<10;i++) { for(int c=0;c<10;c++) { Sleep(3);//延时达到完全随机数的效果 _ftime(&timebuffer); tem=timebuffer.millitm; srand(tem); a=rand()%2; if(rand()%6==1)//再次增加一个随机，增加空格。 { a=0; } Mou[i][c]=a; } cout<<endl; } Mou[0][0]=0; Mou[9][9]=0; for(int e=0;e<10;e++) { for(int d=0;d<10;d++) { if(0==Mou[e][d]) { cout<<"O"<<" "; } else { cout<<Mou[e][d]<<" "; } } cout<<endl; } cout<<endl; if(Makework(Mou)) { cout<<"迷宫有出口，迷宫路线图如下"<<endl; } else { cout<<"迷宫无出口"<<endl; } for(int o=0;o<10;o++) { for(int p=0;p<10;p++) { if(4==Mou[o][p]) { cout<<"*"<<" "; } else if(0==Mou[o][p]) { cout<<"O"<<" "; } else { cout<<Mou[o][p]<<" "; } } cout<<endl; } cout<<"选择1继续，其它退出"<<endl; cin>>quit; } } bool Makework(int Sam[10][10]) { int x=0,y=0;//x横y纵坐标Sam[y][x] int U=-1,D=1,L=-1,R=1;//上下左右 list<int> val; list<int>::iterator vben=val.begin(); list<int>::iterator vend=val.end(); bool back=false;//是否是在后退，当前后左右都不能移动时。 while((9!=x)||(9!=y))//是否到达终点 { if((y+D)<10)//下移动 { if(Sam[y+D][x]==0) { Sam[y][x]=4; if(back)//后退时有新的路线 { Sam[y+D][x]=4;//新路线设置为新起点 back=false; } val.push_back(x);//坐标添加进容器 val.push_back(y); y=y+D;//移动坐标 continue; } } if((x+R)<10)//右移动 { if(Sam[y][x+R]==0) { Sam[y][x]=4; if(back) { Sam[y][x+R]=4; back=false; } val.push_back(x); val.push_back(y); x=x+R; continue; } } if(y+U>=0)//上移动 { if(Sam[y+U][x]==0) { Sam[y][x]=4; if(back) { Sam[y+U][x]=4; back=false; } val.push_back(x); val.push_back(y); y=y+U; continue; } } if((x+L>=0))//左移动 { if(Sam[y][x+L]==0) { Sam[y][x]=4; if(back) { Sam[y][x+L]=4; back=false; } val.push_back(x); val.push_back(y); x=x+L; continue; } } if(!val.empty())//前后左右不能移动或者移动后都有阻挡，那么后退。 { back=true; list<int>::iterator vend=val.end(); --vend; y=*vend; --vend; x=*vend;//修改坐标 val.pop_back(); val.pop_back(); continue; } else { return false; } } return true; }