![cover](https://img-blog.csdnimg.cn/direct/2f3de9d2b0dc420aa9e0248bdf7aaf37.png)
蓝桥杯每日一题 走迷宫bfs 超超详细解释!!!
昨天学习了bfs的基本概念,今天来做一道经典习题练练手吧!
·
昨天学习了bfs的基本概念,今天来做一道经典习题练练手吧!
PS: 文章主要参考:b站 一只会code的小金鱼 的视频(真的讲得超级超级详细!!!很适合大一没接触过算法的小白学习,而且up的声音也很好听很好听!!!墙裂推荐!)
bfs常用的两类题型
1.从A出发是否存在到达B的路径(dfs也可)
2.从A出发到B的最短路径(数小:<20才能用dfs)
遗留的那个问题的答案-
题目:走迷宫
答案:
//走迷宫
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int,int> PII;
const int N=110;
int n,m;
int g[N][N];
int dist[N][N];
queue<PII> q;//队列
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};//上右下左
int bfs(int x1,int y1)
{
memset(dist,-1,sizeof dist);//初始化为-1
q.push({x1,y1});
dist[x1][y1]=0;
while(q.size()&&!q.empty())//队列不空,继续循环
{
PII t =q.front();//取出队头
q.pop();
for(int i=0;i<4;i++)
{
int a=t.first+dx[i];
int b=t.second+dy[i];
//换方向
if(a<1||a>n||b<1||b>m) continue;//越界
if(g[a][b]!=0) continue;
if(dist[a][b]>0) continue;
q.push({a,b});
dist[a][b]=dist[t.first][t.second]+1;
if(a==n&&b==m)
{
return dist[n][m];
}
}
}
return dist[n][m];
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&g[i][j]);
}
}
int res=bfs(1,1);
printf("%d\n",res);
return 0;
}
在coding中遇到的问题:
作为一个不太聪明的小白,在看懂这段代码以及练习过程中自然是遇到了很多很多的问题,在此记录一下 ~
1.memset(dist,-1,sizeof dist);
memset是一个初始化函数,作用是将某一块内存中的全部设置为指定的值。
void *memset(void *s, int c, size_t n);
- s指向要填充的内存块。
- c是要被设置的值。
- n是要被设置该值的字符数。
- 返回类型是一个指向存储区s的指针。
2.代码运行过程(仅供参考)
有些许潦草,哎
3.要点梳理
你学会了吗?
更多推荐
所有评论(0)