广度优先搜索

广度优先搜索算法(英语:Breadth-First-Search,简称BFS),又称宽度优先搜索,是一种图形搜索算法。简单的说,BFS是从根节点开始,沿着树的宽度遍历树的节点。如果所有节点均被访问,则算法中止。[wikipedia]

关键词:广度优先搜索-广搜-宽搜-队列

乳草的入侵
最基本的广搜题目

迷宫问题(waiting for vjudge)

此题目为广度优先搜索问题,复杂之处在于要求输出走路路径,因此需要记录每一步走过的状态,而且要求从(0,0)输出路径,因此需要递归输出,过着记录后统一输出,为了省略代码题解使用递归输出。
关键词:记录路径
代码如下:

#include <cstdio>
#include <iostream>
#include <cstring>
#define MAXN 5

using namespace std;

int pathx[MAXN*MAXN], pathy[MAXN*MAXN], //存储每次走的坐标
    record[MAXN*MAXN]; //记录坐标之间的关系(当前坐标上一步是哪)

void out(int i)
{
    int temp = record[i];

    if (temp != -1) //递归输出路线
        out(temp);
    else
    {
        printf("(%d, %d)\n",pathx[i], pathy[i]);
        return;
    }

    printf("(%d, %d)\n",pathx[i], pathy[i]);
}

int main()
{
    int dx[4] = {0, 1, 0, -1}, //up right down left
        dy[4] = {1, 0, -1, 0}, //up right down left
        __MAP[MAXN][MAXN], //存地图
        visited[MAXN][MAXN], //是否访问过标记
        i, j, k, head = 0, tail = 1;

    for (i = 0; i < MAXN; i++)
        for (j = 0; j < MAXN; j++)
            cin >> __MAP[i][j];

    memset(visited, 0, sizeof(visited)); //初始化
    pathx[0] = 0;
    pathy[0] = 0;
    record[0] = -1;

    while(head < tail) //队列不为空
    {
        if (pathx[head] == 4 && pathy[head] == 4)
            break;
        for (k = 0; k < 4; k++)
        {
            i = pathx[head] + dx[k];
            j = pathy[head] + dy[k];
            if(i<0||j<0||i>4||j>4||__MAP[i][j]||visited[i][j]) //试探,若边界或者已经走过则放弃
                continue;
            else //不是边界并且没有走过则走出一步
            {
                visited[i][j] = 1; //标记已经过
                pathx[tail] = i;
                pathy[tail] = j;
                record[tail] = head; //当前这一步是从哪走过来的
                tail++;
            }
        }
        head++;
    }

    out(head); //输出路线

    return 0;
}

Tag: 广搜, 广度优先搜索, acm

Leave a new comment