献给阿尔吉侬的花束( 入门级bfs查找 + 模版解读 + 错误示范)

2023-09-14 11:36:57

献给阿尔吉侬的花束问题

文章目录

前言

许多小伙伴刚刚接触到 bfs 算法时可能会觉得步骤比较繁琐，所以这里找了一道入门级的 bfs算法题为大家介绍模版，同时引入错误的样例为大家答疑解惑，有其他没列举的情况可以在评论区留言啦。小伙伴们如果感兴趣可以给博主点个关注啦。

题目描述

阿尔吉侬是一只聪明又慵懒的小白鼠，它最擅长的就是走各种各样的迷宫。

今天它要挑战一个非常大的迷宫，研究员们为了鼓励阿尔吉侬尽快到达终点，就在终点放了一块阿尔吉侬最喜欢的奶酪。

现在研究员们想知道，如果阿尔吉侬足够聪明，它最少需要多少时间就能吃到奶酪。

迷宫用一个 R×C的字符矩阵来表示。

字符 S 表示阿尔吉侬所在的位置，字符 E 表示奶酪所在的位置，字符 # 表示墙壁，符 . 表示可以通行。

阿尔吉侬在 1 个单位时间内可以从当前的位置走到它上下左右四个方向上的任意一位置，但不能走出地图边界。

输入格式
第一行是一个正整数 T，表示一共有 T 组数据。

每一组数据的第一行包含了两个用空格分开的正整数 R
和 C，表示地图是一个 R×C 的矩阵。

接下来的 R 行描述了地图的具体内容，每一行包含了 C 个字符。字符含义如题目描述中所述。保证有且仅有一个 S 和 E。

输出格式
对于每一组数据，输出阿尔吉侬吃到奶酪的最少单位时间。

若阿尔吉侬无法吃到奶酪，则输出“oop!”（只输出引号里面的内容，不输出引号）。

每组数据的输出结果占一行。

数据范围
1<T≤10,
2≤R,C≤200
输入样例：

3
3 4
.S..
###.
..E.
3 4
.S..
.E..
....
3 4
.S..
####
..E.

输出样例：

5
1
oop!

题目分析

方法判定

很明显的最短路劲查找问题，所以果断采用 bfs 算法。

bfs 算法模版介绍

两个数组【记录地图，记录移动距离】
int d[N][N];
char g[N][N];
一个队列【依次遍历所有接触到的点】
	queue<PII> q;
    d[st.first][st.second]=0;
    q.push(st);
一次遍历

以当前队列头元素为基点向其他方向扩散，其他方向可以用数组来代替

int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};

while(!q.empty()){
        auto t=q.front();
        q.pop();
        for(int i=0;i<4;i++){
            int x=t.first+dx[i];
            int y=t.second+dy[i];
            
        }
    }

遍历过程中根据要求对遍历到的点进行筛选，筛选成功后记得放入队列，更新dis数组

if(x,y 符合要求，){
	q.push(遍历到的点)；
	更新dis数组
}

模版代码如下;

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N =110;
int g[N][N],d[N][N];
int n,m;
typedef pair<int,int> PII;
queue<PII> q;
int bfs(){
    memset(d,-1,sizeof d);
    d[0][0]=0;
    q.push({0,0});
    int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
    while(!q.empty()){
        PII t=q.front();
        q.pop();
        
        for(int i=0;i<4;i++){
            int x=t.first+dx[i],y=t.second+dy[i];
            if(x>=0&&x<n&&y>=0&&y<m&&d[x][y]==-1 && g[x][y]==0){
                q.push({x,y});
                d[x][y]=d[t.first][t.second]+1;
                
            }
        }
    }
    return d[n-1][m-1];
}
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin>>g[i][j];
    cout<<bfs()<<endl;
    return 0;
}

题解代码

详细的解释都在代码当中，如果还有不明白的在评论区说明即可。

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N = 210;
int t,r,c;
typedef pair<int,int> PII;
int d[N][N];
char g[N][N];//
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
void bfs(PII st){
    queue<PII> q;
    d[st.first][st.second]=0;
    q.push(st);
    //上面是队列的初始化
    //下面正式开始遍历
    while(!q.empty()){
        auto t=q.front();
        q.pop();
        for(int i=0;i<4;i++){
            int x=t.first+dx[i];
            int y=t.second+dy[i];
            if(g[x][y]=='#') continue;
            if(g[x][y]=='.'){
            //走过之后由于是在求最短路劲，所以将走过的路封死
                d[x][y]=d[t.first][t.second]+1;
                g[x][y]='#';
                q.push({x,y});
            }
            if(g[x][y]=='E'){//走到目标点之后一定及时返回
                cout<<d[t.first][t.second]+1<<endl;
                return ;
            }
        }
    }
    //多次循环后无果则没有办法输出对应结果
    cout<<"oop!"<<endl;
}
int main(){
    cin>>t;
    while(t--){
        memset(g,'#',sizeof g);//输入前先将地图初始化，
        //这里为了不处理边界问题，将地图全部设为墙壁
        //如果不这样做就需要处理边界问题,解决方法如下：
        //if(x>=1 && x<=r && y>=1 && y<= c && g[i][j] != '#')
        
        memset(d,0,sizeof d);
        cin>>r>>c;
        PII st;
        for(int i=1;i<=r;i++){
            for(int j=1;j<=c;j++){
                cin>>g[i][j];
                if(g[i][j]=='S'){//找到最开始的那个点
                
                    st={i,j};
                    g[i][j]='#';//由于可以将开始的点视为走过了，
                    //直接将其变成墙壁
                }
                
            }
        }
        bfs(st);
    }
}

错误示范

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N =210;
char g[N][N];
int d[N][N];
int t,r,c;
typedef pair<int,int> PII;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
void bfs(PII st){
    queue<PII> q;
    q.push(st);
    d[st.first][st.second]=0;
    while(!q.empty()){
        auto t=q.front();
        q.pop();
        for(int i=0;i<4;i++){
            int x=t.first+dx[i];
            int y=t.second+dy[i];
            if(g[x][y]=='#') continue;
            if(g[x][y]=='.'){
                q.push({x,y});
                d[x][y]=d[t.first][t.second]+1;
            }
            if(g[x][y]=='E'){
                cout<<d[t.first][t.second]+1<<endl;
                return ;
            }
        }
    }
    cout<<"oop!"<<endl;
}
int main(){
    cin>>t;
    while(t--){
        memset(d,0,sizeof d);
        memset(g,'#',sizeof g);
        PII st;
        cin>>r>>c;
        for(int i=1;i<=r;i++){
            for(int j=1;j<=c;j++){
                cin>>g[i][j];
                if(g[i][j]=='S'){
                    g[i][j]='#';
                    st={i,j};
                }
            }
        }
        bfs(st);
    }
}

这里错在：没有及时将走过的路封死，导致不断循环走过的路

if(g[x][y]=='.'){
                q.push({x,y});
                d[x][y]=d[t.first][t.second]+1;
            }

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N =210;
char g[N][N];
int d[N][N];
int t,r,c;
typedef pair<int,int> PII;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
void bfs(PII st){
    queue<PII> q;
    q.push(st);
    d[st.first][st.second]=0;
    while(!q.empty()){
        auto t=q.front();
        
        for(int i=0;i<4;i++){
            int x=t.first+dx[i];
            int y=t.second+dy[i];
            if(g[x][y]=='#') continue;
            if(g[x][y]=='.'){
                q.push({x,y});
                g[x][y]='#';
                d[x][y]=d[t.first][t.second]+1;
            }
            if(g[x][y]=='E'){
                cout<<d[t.first][t.second]+1<<endl;
                return ;
            }
        }
    }
    cout<<"oop!"<<endl;
}
int main(){
    cin>>t;
    while(t--){
        memset(d,0,sizeof d);
        memset(g,'#',sizeof g);
        PII st;
        cin>>r>>c;
        for(int i=1;i<=r;i++){
            for(int j=1;j<=c;j++){
                cin>>g[i][j];
                if(g[i][j]=='S'){
                    g[i][j]='#';
                    st={i,j};
                }
            }
        }
        bfs(st);
    }
}

这里错在没有及时将队列当中使用过的点弹出，导致Time Limited Exceed

while(!q.empty()){
        auto t=q.front();
//        应该将点弹出！！！！
//		q.pop();
        for(int i=0;i<4;i++){

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N = 210;
int t,r,c;
typedef pair<int,int> PII;
int d[N][N];
char g[N][N];//
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
void bfs(PII st){
    queue<PII> q;
    d[st.first][st.second]=0;
    q.push(st);
    //上面是队列的初始化
    //下面正式开始遍历
    while(!q.empty()){
        auto t=q.front();
        q.pop();
        for(int i=0;i<4;i++){
            int x=t.first+dx[i];
            int y=t.second+dy[i];
            if(g[x][y]=='#') continue;
            if(g[x][y]=='.'){
            //走过之后由于是在求最短路劲，所以将走过的路封死
                d[x][y]=d[t.first][t.second]+1;
                g[x][y]='#';
                //q.push({x,y});
            }
            if(g[x][y]=='E'){//走到目标点之后一定及时返回
                cout<<d[t.first][t.second]+1<<endl;
                return ;
            }
        }
    }
    //多次循环后无果则没有办法输出对应结果
    cout<<"oop!"<<endl;
}
int main(){
    cin>>t;
    while(t--){
        memset(g,'#',sizeof g);//输入前先将地图初始化，
        //这里为了不处理边界问题，将地图全部设为墙壁
        //如果不这样做就需要处理边界问题,解决方法如下：
        //if(x>=1 && x<=r && y>=1 && y<= c && g[i][j] != '#')
        
        memset(d,0,sizeof d);
        cin>>r>>c;
        PII st;
        for(int i=1;i<=r;i++){
            for(int j=1;j<=c;j++){
                cin>>g[i][j];
                if(g[i][j]=='S'){//找到最开始的那个点
                
                    st={i,j};
                    g[i][j]='#';//由于可以将开始的点视为走过了，
                    //直接将其变成墙壁
                }
                
            }
        }
        bfs(st);
    }
}

这里错在没有将符合条件的点及时插入队列，更新队列：

if(g[x][y]=='.'){
            //走过之后由于是在求最短路劲，所以将走过的路封死
                d[x][y]=d[t.first][t.second]+1;
                g[x][y]='#';
                //q.push({x,y});
            }

总结

以上就是关于 bfs 入门算法的全部内容啦，不知道提到的那些错误示范有没有帮助到你呢？有帮助的话可以点个赞+关注吗=͟͟͞͞ʕ•̫͡ ·ʔ=͟͟͞͞ʕ•̫͡ ·ʔ=͟͟͞͞ʕ•̫͡ ·ʔ=͟͟͞͞ʕ•̫͡ ·ʔ=͟͟͞͞

更多推荐

LeetCode 39. Combination Sum【回溯,剪枝】中等

本文属于「征服LeetCode」系列文章之一，这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁，本系列将至少持续到刷完所有无锁题之日为止；由于LeetCode还在不断地创建新题，本系列的终止日期可能是永远。在这一系列刷题文章中，我不仅会讲解多种解题思路及其优化，还会用多种编程语言实现题解，涉及

Android.bp常用语法和预定义属性

介绍Android.bp是Android构建系统中用于定义模块和构建规则的配置文件，它使用一种简单的声明式语法。以下是Android.bp的一些常见语法规则和约定：注释：单行注释使用//符号。多行注释使用/和/包围。和go语言相同//这是单行注释/*这是多行注释*/模块定义：每个模块都以module_type字段开始，

hadoop集群搭建

vim/etc/hosts192.168.1.2Master.Hadoop192.168.1.3Slave1.Hadoop192.168.1.4Slave2.Hadoop192.168.1.5Slave3.Hadoop若能用主机名进行ping通，说明刚才添加的内容，在局域网内能进行DNS解析。hadoop:https:

【iOS】浅析static，const，extern关键字

文章目录前言一、staticstatic修饰局部变量static修饰全局变量总结二、const三、extern声明全局变量声明函数在头文件中使用总结前言笔者本周在学习单例模式时，用到了static关键字，特此总结博客记录学习static，const，extern关键字的过程一、staticstatic——静态，我们将用

【golang】实现通用的get/post请求（接受一个 URL 和一个结构体参数）

通用的GET请求实现一个通用的GET请求函数，该函数接受一个URL和一个结构体参数，并将结构体参数编码为查询参数。以下是一个通用的示例代码：packagemainimport("fmt""net/http""net/url""reflect""strings")funcgetFunc(baseUrlstring,str

Learn Prompt-ChatGPT 精选案例:简单介绍

恭喜你!现在你已经学会了如何编写提示语。本节主要讨论的是如何使用提示语来解决我们在日常或工作中遇到的任务。如果你已经有了一个提示语集，如何决定哪些提示语适合手头的任务？在本节中，我们将通过一些实际例子来给你提供灵感。在挑选案例的时候，我们更加希望展示的是如何将复杂的工作任务拆解成相互关联的小任务。例如在PPT制作中，我

【C++代码】平衡二叉树，二叉树的所有路径，左叶子之和--代码随想录

题目：平衡二叉树给定一个二叉树，判断它是否是高度平衡的二叉树。一棵高度平衡二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。题解这道题中的平衡二叉树的定义是：二叉树的每个节点的左右子树的高度差的绝对值不超过1，则二叉树是平衡二叉树。根据定义，一棵二叉树是平衡二叉树，当且仅当其所有子树也都是平衡二叉

解决Java应用程序中的SQLException：Access denied for user ‘root‘@‘localhost‘ 错误

目录问题背景解决方案如何重置MySQLroot密码：问题背景java.sql.SQLException:Accessdeniedforuser'root'@'localhost'(usingpassword:YES)atcom.mysql.cj.jdbc.exceptions.SQLError.createSQLExc

CSS复习之选择器

目录一、常用选择器1.1元素选择器1.2id选择器1.3class选择器二、复合选择器2.1交集选择器2.2并集选择器三、关系选择器3.1子元素选择器3.2后代选择器3.3兄弟选择器四、属性选择器五、伪类选择器六、伪元素的选择器七、超链接的伪类一、常用选择器1.1元素选择器作用:根据标签名来选中指定的元素语法:标签名{

固定资产管理措施怎么写

固定资产管理措施是指企业在进行固定资产管理时所采取的各种措施和方法。以下是一些常见的固定资产管理措施：加强固定资产的安全保护。该公司采取了多种安全措施建立完善的固定资产管理制度。制定明确的资产采购、使用、维护、报废等流程和标准，确保资产管理的规范性和透明度。采用先进的资产管理软件。通过数字化手段对固定资产进行管理和监控

unity打包后无法读取Excel解决方法

一、前言最近几乎遇到了所有能遇到的unity读取Excel的问题。因为使用的是unity5.4，而且还是32位。所以出现各种问题在所难免。废话不多说，现有的现象是：在unity的编辑器里可以完美运行，读取Excel不成问题，但是打包成exe后就无法读取到对应路径下的Excel表格了。二、解决办法第一种，未能解决：在脚本

热文推荐
  1. 亿图脑图移动端V7.0.0推出一键生成竖屏海报，提升思维导图在手机上的阅读体验

    近日，亿图脑图移动端V7.0.0版本上线，支持思维导图一键生成竖版海报，开拓了一种新的图文表现形式。思维导图作为一种便捷的可视化工具，被广泛应用于日常生活和工作场合中，然而，在手机终端成为主导的竖屏阅读时代，思维导图往往会出现排版复杂，显示效果不佳等问题，这严重影响了用户的使用体验和效率。所以，亿图脑图移动端V7.0.

  2. 算法通关村第13关【白银】| 数字与数学高频问题

    数组实现加法1.加一思路：不进位末尾加一，进位挨个加一99,999...进位，新建长度+1的数组，res[0]=1，直接返回lassSolution{publicint[]plusOne(int[]digits){for(inti=digits.length-1;i>=0;i--){intnum=++digits[i]

  3. Direct3D融合技术

    该技术能使我们将当前要进行光栅化的像素的颜色与先前已已光栅化并处于同一位置的像素的颜色进行合成，即将正在处理的图元颜色值与存储在后台缓存中的像素颜色值进行合成(混合)，利用该技术我们可得到各种各样的效果，尤其是透明效果。在融合运算时需要遵循：首先绘制那些不需要进行融合的物体，然后将需要进行融合的物体按照相对于摄像机的深

  4. 低代码之JeecgBoot

    JeecgBootJeecgBoot是一款基于BPM的低代码平台！前后端分离架构SpringBoot2.x，SpringCloud，AntDesign&Vue，Mybatis-plus，Shiro，JWT，支持微服务。强大的代码生成器让前后端代码一键生成，实现低代码开发！JeecgBoot引领新低代码开发模式Onlin

  5. 【网络协议】Http-下

    因为Http是无状态的，所以为了协助Web保持状态，Cookie诞生了。下面中是百度百科关于Cookie和Session的解释：Cookie：举例来说,一个Web站点可能会为每一个访问者产生一个唯一的ID,然后以Cookie文件的形式保存在每个用户的机器上。如果使用浏览器访问Web,会看到所有保存在硬盘上的Cookie

  6. 【Git】03-GitHub

    文章目录1.GitHub核心功能2.GitHub搜索项目3.GitHub搭建个人博客4.团队项目创建5.git工作流选择5.1需要考虑的因素5.2主干开发5.2GitFlow5.3GitHubFlow5.4GitLabFlow(带生产分支)5.4GitLabFlow(带环境分支)5.4GitLabFlow(带发布分支)

  7. Ceph入门到静态-deep scrub 深度清理处理

    9.6洗刷REPORTDOCUMENTATIONBUG#除了为对象创建多个副本外，Ceph还可通过洗刷归置组来确保数据完整性（请参见第1.3.2节“归置组”了解有关归置组的详细信息）。Ceph的洗刷类似于在对象存储层运行fsck。对于每个归置组，Ceph都会生成一个包含所有对象的编目，并比较每个主对象及其副本，以确保不

  8. 如何解决 Spring Boot Actuator 的未授权访问漏洞

    SpringBootActuator的作用是提供了一组管理和监控端点，允许你查看应用程序的运行时信息，例如健康状态、应用程序信息、性能指标等。这些端点对于开发、测试和运维团队来说都非常有用，可以帮助快速诊断问题、监控应用程序的性能，并采取必要的措施来维护和管理应用程序。SpringBootActuator未授权访问的配

  9. LeetCode 40. Combination Sum II【回溯,剪枝】中等

    本文属于「征服LeetCode」系列文章之一，这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁，本系列将至少持续到刷完所有无锁题之日为止；由于LeetCode还在不断地创建新题，本系列的终止日期可能是永远。在这一系列刷题文章中，我不仅会讲解多种解题思路及其优化，还会用多种编程语言实现题解，涉及