CC++广度优先搜索模拟迷宫求解问题

问题描述

用一个字符类型的二维数组表示迷宫，数组中的每个元素表示一个小方格，‘0’代表通道，‘1’代表阻塞物。设计一个模拟小动物走迷宫的程序，为小动物寻找一条从迷宫入口到迷宫出口的通路。

功能及界面要求：

用户可以设置迷宫的行数或列数。随机产生迷宫的状态。用户设置小动物的入口下标和出口下标根据迷宫状态和入、出口位置直观显示出从入口到出口的通路或“不存在通路”的信息。

代码

重要的点已经注释了, 就不在多说了, 有什么问题可以下方评论区进行讨论.

#include<cstdio> #include<cstdlib> #include<ctime> #include<iostream> using namespace std; long map[10000][10000]; int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; //可走的四个方向 struct node { int x,y; }; struct node queue[5000], record[5000][5000];//queue记录可走的点，广搜； //record记录改点的前驱 bool bfs(int column, int row, int startx, int starty, int endpx, int endpy) { int head, tail, i; struct node cur, next;//cur为当前位置，next为下一个位置 head = tail = 0; //head = startx - 1; //tail = starty - 1; cur.x = queue[tail].x; cur.y = queue[tail].y; tail++; while(head < tail) { cur = queue[head++]; for(i = 0; i < 4; i++) { next.x = cur.x+dir[i][0]; next.y = cur.y+dir[i][1]; if(next.x>=0 && next.y>=0 && next.x<column && next.y<row && map[next.x][next.y] == 0) { record[next.x][next.y].x = cur.x; record[next.x][next.y].y = cur.y;//记录next的前驱，即next的坐标（因为next记录的是第一个到达该地点的前驱，随后被标记走过，故不用担心被后来的前驱坐标所覆盖） if(next.x == endpx && next.y == endpy) return true; else { map[next.x][next.y] = 1;//标记走过 queue[tail++] = next; } } } } return false; } int main() { int i, j; int k, m, n, flag = 0; int save, column, row, startx,starty,endpx, endpy; struct node cur; while(!flag) { cout<<"请输入行和列"<<endl; cout<<"行为: "; cin>>column; cout<<"列为: "; cin>>row; cout<<"起始位置: "; scanf("%d%d", &startx, &starty); cout<<"终点: "; scanf("%d%d", &endpx, &endpy); srand(time(NULL)); for(i = 0; i < column; i++) { for(j = 0; j < row; j++) { save = (int)(rand()%10 > 2 ? 0:1); map[i][j] = save; printf("-", save); } cout<<endl; } if(map[startx][starty] == 1) { printf("无路径!!!\n"); flag = 0; } else { cur.x = startx; cur.y = starty; map[startx][starty] = 1; queue[0] = cur;//可走的点为当前结点 if(!bfs(column, row, startx, starty, endpx, endpy)) {printf("无路径!!!\n"); flag = 0;} else { k = 0; queue[k].x = endpx; queue[k++].y = endpy; i = endpx; j = endpy; while(i!=startx || j!=starty)//根据record的记录，从后往前回溯其路径，并存在queue中 { m = i; n = j; i = record[m][n].x; j = record[m][n].y; queue[k].x = i; queue[k++].y = j; } for(i = k-1; i >= 0; i--)//输出路径 printf("(%d, %d)\n",queue[i].x,queue[i].y); flag = 1; return 0; } } } }