[算法训练-初级篇]1. 广度优先搜索

个人理解:从某元素开始搜索,搜索该元素的所有方向,把符合条件的方向的元素"入队"...然后从队列中取出一个元素,对这个元素进行全方向搜索,,符合条件的加入队列..........直到符合结束条件或者队空.

应用:常用于最短路径问题,,


例题;(迷宫的最短路径问题):
给定一个大小为N*M的迷宫,迷宫由通道和墙壁组成, 每步可以向相邻的的上下左右四个通道移动, 请求出从起点到终点所需的最小步数.(假定从起点一定可以到终点)<限制:N, M <= 100>

const int INF = 100000000;            /*int类型可以那么大吗?*/
typedef pair<int, int> p;
char maze[MAX_N][MAX_M + 1];
int N;
int M;
int sx;                                /*起始坐标*/
int sy;
int gx;                                /*终点坐标*/
int gy;

int d[MAX_N][MAX_M];

int dx[4] = {1, 0, -1, 0};                /*右下左上,
int dy[4] = {0, 1, 0, -1};

int bfs()
{
    int nx = 0;
    int ny = 0;
    queue<p> que;                        /*p是前面的pair类型*/

    for (int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            d[i][j] = INF;
        }
    }
    que.push(p(sx, sy));
    d[sx][sy] = 0;

    while (que.size())
    {
        p pp = que.front();                /*查看最前面那个数, p为pair类型*/
        que.pop();                        /*清除最前面那个数(

        if (pp.first == gx && pp.second == gy)
        {
            break;                                /*到达终点*/
        }

        for (int i = 0; i < 4; i++)
        {
            nx = pp.first + dx[i];
            ny = pp.second + dy[i];

            if ((0 <= nx && nx < N) && (0 <= ny && ny < M) && maze[nx][ny] != '#' && d[nx][ny] == INF)            /*不为#(墙), 且没有访问过*/
            {
                que.push(p(nx, ny));            /*入队*/
                d[nx][ny] = d[pp.first][pp.second] + 1;
            }
        }
    }

    return d[gx][gy];
}

void solve()
{
    int res = bfs();
    printf("最短路径为:%d\n", res);
}

结果:

<<每周一算法,健康中国人---------------------------初代.>>