刚学完数据结构，老师让做几个小东西，包括求迷宫最短路径，太简单怎么办，自己给自己加需求咯
首先，求迷宫最短路径，先得要有迷宫吧，不过，手动输入迷宫是不是有点太捞了？
//随机产生迷宫
71 void Readfile_rand(unsigned int seed)
72 {
73
74 //初始化存储迷宫信息的数组
75 for(int i = 0;i < L+2;++i)
76 for(int j = 0;j < L+2;++j) {
77 ar[i][j].property = 1;
78 ar[i][j].access = false;
79 }
80 srand(unsigned(seed));
81 for(int i = 1;i < L+1;++i)
82 for(int j = 1;j < L+1;++j) {
83 ar[i][j].x = 0;
84 ar[i][j].y = 0;
85 ar[i][j].property = (rand())%2 + '0';
86 }
87 ar[1][1].property = '0';
88
89
90 }
利用随机数自己生成迷宫，多帅啊
那么问题来了，怎么能确保生成的迷宫有解呢？
毕竟是随机生成的，有解的可能性不太高，只能用笨方法，
通过不断改变种子，生成多个迷宫，直至找到有解的那个为止
//随机生成可以通过的迷宫
270 for(int i = rand()%1000;i < 10000;++i) {
271 Init();
272 Readfile_rand(i);
273 if(Findway() == 1) {
274 break;
275 }
276 }
终于到了老师要求的部分了，论迷宫找路
//非递归遍历迷宫找到出路
struct data{
int x;
int y;
};
int Findway()
{
list<struct data> lst;
lst.push_back({1,1});
ar[1][1].access = true;
while(ar[L][L].access == false && !lst.empty()) {
auto p = lst.begin();
int x = p->x;
int y = p->y;
if(ar[x][y-1].property == '0' && ar[x][y-1].access == false) {
lst.push_back({x,y-1});
ar[x][y-1].x = x;
ar[x][y-1].y = y;
ar[x][y-1].access = true;
}
if(ar[x][y+1].property == '0' && ar[x][y+1].access == false) {
lst.push_back({x,y+1});
ar[x][y+1].x = x;
ar[x][y+1].y = y;
ar[x][y+1].access = true;
}
if(ar[x-1][y].property == '0' && ar[x-1][y].access == false) {
lst.push_back({x-1,y});
ar[x-1][y].x = x;
ar[x-1][y].y = y;
ar[x-1][y].access = true;
}
if(ar[x+1][y].property == '0' && ar[x+1][y].access == false) {
lst.push_back({x+1,y});
ar[x+1][y].x = x;
ar[x+1][y].y = y;
ar[x+1][y].access = true;
}
lst.pop_front();
}
//输出迷宫出路路径
if(ar[L][L].access == true) {
for(int i = 1;i < L+1;++i)
for(int j = 1;j < L+1;++j)
ar[i][j].access = false;
int i = L,j = L;
while(1) {
ar[i][j].access = true;
int x = ar[i][j].x;
int y = ar[i][j].y;
i = x;
j = y;
if(i == 1 && j == 1)
break;
}
ar[1][1].access = true;
return 1;
}
else
return 0;
}关于中间四个if,其实可以省略为一个，不过为了方便（其实是懒得搞），就这样了
算法其实也没什么好讲的，这里使用了双向链表代替了队列的作用
１．头结点入队
２．队头结点四个方向可以走的位置全部入队
３．队头结点出队
４．执行２步骤，直到我们的终点标记为已访问或队列为空
就是简单的非递归实现ＢＦＳ
那么我的需求加在哪里了呢，在这儿
void Stand_Alone(char diff)
217 {
218 //从0,0开始
219 ar[0][0].access = true;
220 int x = 1;
221 int y = 1;
222 char choice;
223 Print_alone(1,1,diff);
224 while(ar[L][L].access != true && (choice = getch())) {
225 if(choice == 65 && x-1 >= 1 && ar[x-1][y].property == '0') {
226 ar[x][y].access = false;
227 x -= 1;
228 }
229 if(choice == 66 && x+1 <= L && ar[x+1][y].property == '0') {
230 ar[x][y].access = false;
231 x += 1;
232
233 }
234 if(choice == 67 && y+1 <= L && ar[x][y+1].property == '0') {
235 ar[x][y].access = false;
236 y += 1;
237 }
238 if(choice == 68 && y-1 >= 1 && ar[x][y-1].property == '0') {
239 ar[x][y].access = false;
240 y -= 1;
241 }
242 if(choice == 't') {
243 system("clear");
244 Init();
245 Findway();
246 Print();
247 }
248 ar[x][y].access = true;
249 system("clear");
250 Print_alone(x,y,diff);
251 cout << x << "," << y << " " << "终点:" << L << "," << L << endl;
252 cout << "t.提示" << endl;
253 }
254
255 system("clear");
256 Print();
257 cout << "成功！！！" << endl;
258 }
初始位置为１，１ 为了到达终点，需要自己控制上下左右，也就是说是个一般的迷宫游戏，到达终点则游戏结束
不过要是一般的简单迷宫，不夸张的说，眼睛遍历都给它能遍历出出路，所以，又加了一点点难度选项’
正如上面看到的那样，函数参数用于控制游戏难度，难度具体体现在哪些方面呢
void Print_alone(int x,int y,char diff)
194 {
195 for(int i = 1;i < L+1;++i) {
196 for(int j = 1;j < L+1;++j) {
197 if(i >= x+'a'-diff && i <= x-'a'+diff && j >= y+'a'-diff && j <= y-'a'+diff) {
198
199 if(ar[i][j].access == true)
200 cout << "_";
201 else {
202 if(ar[i][j].property == '0')
203 cout << "@";
204 else
205 cout << "#";
206
207 }
208 }
209 else
210 cout << " ";
211 }
212 cout << endl;
213 }
214 }
这个函数用来显示此时“行走"的情况，若参数为困难，则每次只会显示出玩家当前所在格，其他整个迷宫则都为空
中等的话是会显示出玩家所在九宫格，而随机生成的迷宫，要求应该是不低于16*16的
没有学习过图形库，纯字符界面确实丑陋，试着看能不能加上去
其实也是为了好玩，毕竟纯粹只按老师说的搞太无趣了
下面是整个的源代码，感觉还可以抢救一下
#include <iostream>
#include <stack>
#include <fstream>
#include <vector>
#include <deque>
#include <list>
#include <stdlib.h>
#define L 16
using namespace std;
typedef struct{
char property; //结点属性
bool access; //结点是否被访问
int x; //上一个结点的坐标
int y;
}Maze;
#include <termio.h>
int getch(void)
{
struct termios tm, tm_old;
int fd = 0, ch;
if (tcgetattr(fd, &tm) < 0) {//保存现在的终端设置
return -1;
}
tm_old = tm;
cfmakeraw(&tm);//更改终端设置为原始模式，该模式下所有的输入数据以字节为单位被处理
if (tcsetattr(fd, TCSANOW, &tm) < 0) {//设置上更改之后的设置
return -1;
}
ch = getchar();
if (tcsetattr(fd, TCSANOW, &tm_old) < 0) {//更改设置为最初的样子
return -1;
}
return ch;
}
Maze ar[L+2][L+2];
void Init()
{
//初始化迷宫数组
for(int i = 0;i < L+2;++i)
for(int j = 0;j < L+2;++j)
ar[i][j].access = false;
}
void Print()
{
for(int i = 1;i < L+1;++i) {
for(int j = 1;j < L+1;++j)
if(ar[i][j].property == '0') {
if(ar[i][j].access == false)
cout << "@";
else
cout << "_";
}
else
cout << "#";
cout << endl;
}
}
//随机产生迷宫
void Readfile_rand(unsigned int seed)
{
//初始化存储迷宫信息的数组
for(int i = 0;i < L+2;++i)
for(int j = 0;j < L+2;++j) {
ar[i][j].property = 1;
ar[i][j].access = false;
}
srand(unsigned(seed));
for(int i = 1;i < L+1;++i)
for(int j = 1;j < L+1;++j) {
ar[i][j].x = 0;
ar[i][j].y = 0;
ar[i][j].property = (rand())%2 + '0';
}
ar[1][1].property = '0';
}
void Readfile()
{
//初始化存储迷宫信息的数组
for(int i = 0;i < L+2;++i)
for(int j = 0;j < L+2;++j) {
ar[i][j].property = '1';
ar[i][j].access = false;
}
fstream ifile("maze.txt");
string data;
int i = 1,j;
while(getline(ifile,data)) {
j = 1;
for(char c : data) {
ar[i][j].x = 0;
ar[i][j].y = 0;
if(c == '@')
ar[i][j++].property = '0';
else
ar[i][j++].property = '1';
}
i++;
}
ifile.close();
}
//非递归遍历迷宫找到出路
struct data{
int x;
int y;
};
int Findway()
{
list<struct data> lst;
lst.push_back({1,1});
ar[1][1].access = true;
while(ar[L][L].access == false && !lst.empty()) {
auto p = lst.begin();
int x = p->x;
int y = p->y;
if(ar[x][y-1].property == '0' && ar[x][y-1].access == false) {
lst.push_back({x,y-1});
ar[x][y-1].x = x;
ar[x][y-1].y = y;
ar[x][y-1].access = true;
}
if(ar[x][y+1].property == '0' && ar[x][y+1].access == false) {
lst.push_back({x,y+1});
ar[x][y+1].x = x;
ar[x][y+1].y = y;
ar[x][y+1].access = true;
}
if(ar[x-1][y].property == '0' && ar[x-1][y].access == false) {
lst.push_back({x-1,y});
ar[x-1][y].x = x;
ar[x-1][y].y = y;
ar[x-1][y].access = true;
}
if(ar[x+1][y].property == '0' && ar[x+1][y].access == false) {
lst.push_back({x+1,y});
ar[x+1][y].x = x;
ar[x+1][y].y = y;
ar[x+1][y].access = true;
}
lst.pop_front();
}
//输出迷宫出路路径
if(ar[L][L].access == true) {
for(int i = 1;i < L+1;++i)
for(int j = 1;j < L+1;++j)
ar[i][j].access = false;
int i = L,j = L;
while(1) {
ar[i][j].access = true;
int x = ar[i][j].x;
int y = ar[i][j].y;
i = x;
j = y;
if(i == 1 && j == 1)
break;
}
ar[1][1].access = true;
return 1;
}
else
return 0;
}
void Print_alone(int x,int y,char diff)
{
for(int i = 1;i < L+1;++i) {
for(int j = 1;j < L+1;++j) {
if(i >= x+'a'-diff && i <= x-'a'+diff && j >= y+'a'-diff && j <= y-'a'+diff) {
if(ar[i][j].access == true)
cout << "_";
else {
if(ar[i][j].property == '0')
cout << "@";
else
cout << "#";
}
}
else
cout << " ";
}
cout << endl;
}
}
void Stand_Alone(char diff)
{
//从0,0开始
ar[0][0].access = true;
int x = 1;
int y = 1;
char choice;
Print_alone(1,1,diff);
while(ar[L][L].access != true && (choice = getch())) {
if(choice == 65 && x-1 >= 1 && ar[x-1][y].property == '0') {
ar[x][y].access = false;
x -= 1;
}
if(choice == 66 && x+1 <= L && ar[x+1][y].property == '0') {
ar[x][y].access = false;
x += 1;
}
if(choice == 67 && y+1 <= L && ar[x][y+1].property == '0') {
ar[x][y].access = false;
y += 1;
}
if(choice == 68 && y-1 >= 1 && ar[x][y-1].property == '0') {
ar[x][y].access = false;
y -= 1;
}
if(choice == 't') {
system("clear");
Init();
Findway();
Print();
}
ar[x][y].access = true;
system("clear");
Print_alone(x,y,diff);
cout << x << "," << y << " " << "终点:" << L << "," << L << endl;
cout << "t.提示" << endl;
}
system("clear");
Print();
cout << "成功！！！" << endl;
}
int main()
{
char choice;
cout << "a.单机模式"<< endl;
cout << "q.退出" << endl;
srand(time(NULL));
while(cin >> choice && choice != 'q') {
switch(choice) {
case 'a':
//随机生成可以通过的迷宫
for(int i = rand()%1000;i < 10000;++i) {
Init();
Readfile_rand(i);
if(Findway() == 1) {
break;
}
}
Init();
char diff;
cout << "选择难度(a.困难 b.中等 c.简单)" << endl;
cin >> diff;
Stand_Alone(diff);
break;
}
cout << "a.单机模式" << endl;
cout << "q.退出" << endl;
}
return 0;
}