昨天学习了bfs的基本概念，今天来做一道经典习题练练手吧！ 

 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);//初始化为-1q.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.要点梳理 

 

你学会了吗？