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

问题描述

用一个字符类型的二维数组表示迷宫，数组中的每个元素表示一个小方格，‘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("%2d", 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;

            }

        }
    }
}