宽度优先搜索和深度优先搜索的区别是，宽度优先要先让当前点横向到达所有可以一步到达的点，判断在这些点中是否有自己需要的终点（注意别重复走，要去重），如果有就停下来，这样可以找出最短路径，如果没有就将这些点放入队列中用于下一次的更新，也就是说每一次都是从一个点开始走到尽可能多的点上去
思路：最小移动次数利用深度优先搜索即可，从开始点开始计算所有一步可以到达的点，打上标记，然后用一步可以到达的点去找所有可以两步到达的点，依此类推直到到达终点。这里需要注意的是，为什么某个点第一次被遍历它就一定是该点据起点的最短路径，这个问题结合队列的特性显而易见。
#include
#include
#include
#include
#include
#define x first
#define y second
using namespace std;
typedef pair PII;
const int N = 110;
int a[N][N];
int dist[N][N];
int n, m;
int bfs()
{
memset(dist, -1, sizeof(dist));//将所有点距离起点的距离标记为-1，意为全部没有被遍历过
dist[0][0] = 0;//将起点的距离改为0，用于后续其它点的距离的更新
queue q;//队列
q.push({0, 0});
int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};//一个点可以走的四个方向的坐标变化
while(q.size())
{
auto t = q.front();
q.pop();
for(int i = 0; i < 4; i ++)
{
int x = t.x + dx[i], y = t.y + dy[i];
if(x >= 0 && x < n && y >= 0 && y < m && a[x][y] == 0 && dist[x][y] == -1)//判断当前点是否越界，是否已经走过了
{
dist[x][y] = dist[t.x][t.y] + 1;
q.push({x, y});
}
}
}
return dist[n - 1][m -1];//返回终点距离起点的距离
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++)
for(int j = 0; j < m; j ++)
scanf("%d", &a[i][j]);
printf("%d\n", bfs());
return 0;
}
Original: https://www.cnblogs.com/amour233/p/16469229.html
Author: LYL233
Title: 宽度优先搜索基础
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/644221/
转载文章受原作者版权保护。转载请注明原作者出处！