BFS求解迷宫问题

女爷i 2022-05-20 06:37 220阅读 0赞

#### 以前学习C的时候，老师布置过一个拓展作业，实现迷宫的求解，当时没有学习数据结构，有点难以下手，现在学完数据结构已经将近2年，终于解决了这个问题。 ####

##### 给定一个n\*m大小的迷宫，其中\*代表不可通过的墙壁，”.”代表平地，S代表起点，T代表终点。每次只能 上下左右移动，求S到T的最短步数。（详见算法笔记P278） #####

##### 这是一个搜索问题，利用BFS实现思路很简单，当从S广搜到T时，当前的层数就是最短的步数。 #####

#include<cstdio>
    #include<cstring>
    #include<queue>
    
    using namespace std;
    
    const int maxn = 100;
    struct Node
    {
        int x, y;
        int step;
    }S, T, node;
    
    int n, m;  //n * m
    char maze[maxn][maxn];
    bool inq[maxn][maxn] = {
       false};
    int X[4] = {
       0, 0, 1, -1};
    int Y[4] = {
       1, -1, 0, 0};
    
    bool test(int x, int y)
    {
        if(x >= n || x < 0 || y >= m || y < 0)
            return false;
        if(maze[x][y] == '*')
            return false;
        if(inq[x][y] == true)
            return false;
        return true;
    }
    
    int BFS()
    {
        queue<Node> q;
        S.step = 0;
        inq[S.x][S.y] = true;
        q.push(S);
    
        while(!q.empty())
        {
            Node top = q.front();
            q.pop();
            if(top.x == T.x && top.y == T.y)
                return top.step;
            for(int i = 0; i < 4; ++i)
            {
                int newX = top.x + X[i];
                int newY = top.y + Y[i];
                if(test(newX, newY))
                {
                    node.x = newX;
                    node.y = newY;
                    node.step = top.step + 1;
                    q.push(node);
                    inq[newX][newY] = true;
                }
    
            }
        }
        return -1;
    }
    
    int main()
    {
        scanf("%d%d", &n, &m);
        for(int i = 0; i < n; ++i)
        {
            getchar();
            for(int j = 0; j < m; ++j)
            {
                maze[i][j] = getchar();
            }
        }
        scanf("%d%d%d%d", &S.x, &S.y, &T.x, &T.y);
        printf("%d\n", BFS());
        return 0;
    }

运行截图：  
![这里写图片描述][70]

[70]: /images/20220520/e45d0ff6889f4a2aaa730057e88aca92.png