献给阿尔吉侬的花束问题
文章目录
前言
许多小伙伴刚刚接触到 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 入门算法的全部内容啦，不知道提到的那些错误示范有没有帮助到你呢？有帮助的话可以点个赞+关注吗=͟͟͞͞ʕ•̫͡ ·ʔ=͟͟͞͞ʕ•̫͡ ·ʔ=͟͟͞͞ʕ•̫͡ ·ʔ=͟͟͞͞ʕ•̫͡ ·ʔ=͟͟͞͞
本文含有隐藏内容，请 开通VIP 后查看