首页 > 其他 > 详细

宽度优先搜索(BFS)

时间:2020-10-16 23:23:48      阅读:31      评论:0      收藏:0      [点我收藏+]

迷宫的最短路径

给定一个大小为N*M的迷宫。迷宫由通道和墙壁组成,每一步可以向领接的上下左右四格的通道移动。请求出起点到终点所需的最小步数。

请注意,本题假定从起点一定可以移动到终点。

限制条件 N,M ≤ 100

 

思路:

借助辅助数组来标记当前位置是否走过,首先将辅助数组全部初始化为INF

定义一个pair,用来装坐标x,y,然后用pair存入队列

首先把开始位置加入队列中,然后把map中开始位置置为0

当队列不为空的时候,取队列头部的pair,然后做一个判断,看当前坐标是否为终点的坐标,如果是就break退出

开始上下左右四个方向的循环遍历,如果当前地图上的值不是#,而且辅助数组是默认值INF的时候,就加入队列。

然后辅助数组中的当前坐标的值变成 前一个出队列的辅助数组坐标中的值 加 1

最后返回辅助数组中终点坐标的值

const int INF = 1000000;
typedef pair<int, int> P;
int sx = 0, sy = 1;
int gx = 9, gy = 8;
int N = 10, M = 10;
int map[10][10];
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,1,0,-1 };
int maze[10][10] = {
    {#,S,#,#,#,#,#,#,.,#},
    {.,.,.,.,.,.,#,.,.,#},
    {.,#,.,#,#,.,#,#,.,#},
    {.,#,.,.,.,.,.,.,.,.},
    {#,#,.,#,#,.,#,#,#,#},
    {.,.,.,.,#,.,.,.,.,#},
    {.,#,#,#,#,#,#,#,.,#},
    {.,.,.,.,#,.,.,.,.,.},
    {.,#,#,#,#,.,#,#,#,.},
    {.,.,.,.,#,.,.,.,G,#}
};

int bfs()
{
    queue<P> q;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            map[i][j] = INF;
        }
    }
    q.push(P(sx, sy));
    map[sx][sy] = 0;
    while (!q.empty())
    {
        P p = q.front();
        q.pop();
        if (p.first == gx && p.second == gy)
        {
            break;
        }
        for (int i = 0; i < 4; i++)
        {
            int nx = p.first + dx[i];
            int ny = p.second + dy[i];
            if (nx >= 0 && nx < N&&ny >= 0 && ny < M&&maze[nx][ny] != #&&map[nx][ny] == INF)
            {
                q.push(P(nx, ny));
                map[nx][ny] = map[p.first][p.second] + 1;
            }
        }
    }
    return map[gx][gy];
}

 

宽度优先搜索(BFS)

原文:https://www.cnblogs.com/yuanjun93/p/13828563.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!