博客

第一次学习BFS案例，做一个迷宫

输入迷宫行和列大小，长宽最大为8，再输入迷宫的地图，0代表可走，1代表不可走。

输入起点和终点位置。注意：起点和终点的行和列数都要+1，例如，3*3的迷宫，要把终点设置在第二行第三列，直接输入2，3，而不是1，2。因为为了避免在遍历上下左右点的时候，出现越界情况，迷宫的上下左右设置了一圈“围墙”，都为不可走（1）。

以下是代码：

#include <iostream>
#include<queue>
using namespace std;
struct Point
{
    int x;
    int y;
    int step;
};
//队列
queue<Point>Record;
int Maze[10][10];//迷宫多加两行和两列，可以防止在后面的时候越界

int main()
{
    
    int row, col;//行，列
    cout << "请输入迷宫的行，列数";
    cin >> row >> col;

    //设置迷宫：（两步）
    // 1、把空白位置全部设置为1，不可走
    for (int i = 0; i < 10; i++)
    {
        for (int j = 0; j < 10; j++)
        {
            Maze[i][j] = 1;
        }
    }
    cout << "请画迷宫地图：";
    //2、预留出第一行和第一列，可以防止越界
    for (int i = 1; i < row+1; i++)
    {
        for (int j = 1; j <col+1; j++)
        {
            
            cin >> Maze[i][j];//给迷宫赋值（0代表可走，1代表不可走）
        }
    }
    
    cout << "请给定终点：";
    //给定终点
    int endx, endy;
    cin >> endx >> endy;

    cout << "请给定起点：";
    //起点
    Point start;
    cin >> start.x>>start.y;//输入起点坐标
    start.step = 0;
    
    //入队
    Record.push(start);


    //定义一个visit[]数组，用于记录该点是否来过（没来过为0，来过为1）
    int visit[8][8];
    for (int i = 0; i < 8; i++)
    {
        for (int j = 0; j < 8; j++)
        {
            visit[i][j] = 0;
        }
    }
    //用于记录有没有答案，0为没有，1为有
    int flag = 0;
    while (!Record.empty())//不为空就循环
    {
        //1、先判断队首是否为终点
        if (Record.front().x == endx && Record.front().y == endy)
        {
            flag = 1;//有答案
            cout << Record.front().step;
            break;
        }
        //2、可扩展点入队
        int movex[4] = {1,-1,0,0};//上下左右，横向移动
        int movey[4] = {0,0,-1,1};//上下左右，竖向移动

        //创建一个临时结构体
        Point temp;
        for (int i = 0; i < 4; i++)
        {
            temp.x = Record.front().x + movex[i];
            temp.y = Record.front().y + movey[i];
            if (Maze[temp.x][temp.y] == 0 && visit[temp.x][temp.y] == 0)//可走，且没来过
            {
                temp.step = Record.front().step + 1;//步数加1
                Record.push(temp);//入队
                visit[temp.x][temp.y] = 1;//设置为来过
            }
        }
        //队首无可扩展点了，出队
        Record.pop();
    }
    if (flag == 0)
    {
        cout << "无答案";
    }
    system("Pause");

}

参考自：BFS广搜解决迷宫问题