广度优先搜索(BFS)
标签: 机试攻略 - 高分篇
学习人数: 25.8k


高清播放
赞赏支持

广度优先搜索其实简单的理解就是从起点开始一层一层的扩散出去,要实现这个一层一层的扩散就要用到队列的先进先出的思想,所以一般我们都用队列来实现广度优先搜索算法。

 

迷宫
题目描述:
小 A 同学现在被困在了一个迷宫里面,他很想从迷宫中走出来,他可以 向上、向下、向左、向右移动、每移动一格都需要花费 1 秒的时间,不能够走到 边界之外。假设小 A 现在的位置在 S,迷宫的出口在 E,迷宫可能有多个出口。 问小 A 想要走到迷宫出口最少需要花费多少秒?
输入描述:
有多组测试数据。
第一行输入两个正整数 H(0 < H <= 100)和 W(0 < W <= 100),分别表示迷
宫的高和宽。
接下来 H 行,每行 W 个字符(其中‘*’表示路,‘#’表示墙,‘S’表示小 A
的位置,‘E’表示迷宫出口)。
当 H 与 W 都等于 0 时程序结束。
输出描述:
输出小 A 走到迷宫出口最少需要花费多少秒,如果永远无法走到出口则输出“-1”。
输入样例#:
3 3
S*#
**#
#*E
0 0
输出样例#:
4
题目来源:
DreamJudge 1563

题目解析:直接使用广度优先搜索模板即可。

 

参考代码

#include <bits/stdc++.h>  
using namespace std;  
  
const int maxn = 100 + 5;
char mpt[maxn][maxn];
int vis[maxn][maxn];
int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
struct node {
    int x, y;
    int step;
};
//使用广度优先搜索求解  
int bfs(int sx, int sy) {
    memset(vis, 0, sizeof(vis));
    queue<node> q;//使用队列来维护一层层发散的优先级  
    q.push(node{sx, sy, 0});
    vis[sx][sy] = 1;
    int ans = -1;
    while(!q.empty()) {
        node now = q.front();
        q.pop();
        if (mpt[now.x][now.y] == 'E') {//找到终点  
            ans = now.step;
            break;
        }
        for (int i = 0; i < 4; i++) {//上下左右四个方向  
            int nx = now.x + dir[i][0];
            int ny = now.y + dir[i][1];
            if ((mpt[nx][ny] == '*' || mpt[nx][ny] == 'E')&&vis[nx][ny] == 0) {
                q.push(node{n...
登录查看完整内容


课后作业

练习题目

DreamJudge 1308 迷宫逃离2
DreamJudge 1124 生化武器2
DreamJudge 1126 生化武器

 


登录后开始许愿

暂无评论,来抢沙发