• 为什么就算有多条通路，它总能输出最小距离？
  因为当第一个点到达终点时，它一定是最短距离，并且会将终点变成墙，那么其他点再也无法到达终点，也更新不了初始点到终点的距离。

说的真好啊！

6

为什么第一个点到达终点后一定是最小距离

这就是bfs的特点，队列中存储的队首元素A出队，假设A的相邻点是终点，那么终点到起点路程=A->起点的路程+1,然后终点就被标记成了走过了，现在队首A出队，B成为新队首，可以根据bfs的特点，后入队的元素的距离都是先入队的元素的距离+1,即B->起点路程 >= A->起点路程,假设B也是终点的相邻点，那么B+1>=A+1肯定不行，因为终点此时已经被标记成了走过了，所以距离值是A+1，而不是B+1,就是最小了。

因为当第一个点到达终点时，终点就被变为了墙，后到达的点无法到达终点，那自然就不会更新距离

这里我问一下是不是不走回头路？

大家看y总的代码，把if语句加一个距离为-1（还没走过）才往下走

海绵宝宝我可爱死你啦！

👌🏻

大佬，请问那一步是保证找到的就是最短的呢，我脑子有点笨看不出来

bfs函数里面的if语句确保了最短距离，图里面只有没走过的点才会向下计算距离，当最短距离出来之后，出口的点就相当于走过了，所以不会有更长的出现了

个人理解，有误请谅解

挺清楚的，谢谢大佬

bfs每个点只遍历一次喔

BFS基本思想决定了第一次到达就是最终的点。因为她是一圈圈遍历的，可以仔细看一下y总视频

意思是每种可能都会走，但是将每一次情况走过时，最短的路径会先到达，而到达时就会结束循环，此时输出的就是最短的路径。但是有点不理解的就是怎样同时将每种情况同时走一遍

我也是这样理解的，但是神奇的是去掉标记走过代码g[start.first][start.second] = 1;也能ac，这是为什么？求解QAQ

因为这句话仅仅是用来将初始点墙掉，而就算不墙，在下一步也会有一个情况重回初始点把初始点墙掉。但不影响结果。

入队的时候，置为了1，出队的时候再置为1，重复了，这句可以去掉

太棒了

最短路径到达后，应该没有立即退出循环吧？应该是标记终点，让其他路径无法到达。

大佬

其实太简单了，bfs是一层一层遍历的。每一层都是上一层状态的一步拓展。

海绵宝宝永远滴神

memset按字节赋值哦，int是四个字节、不能用memset全部初始化为1

写1，存储的不是1,。只要不是 0 或 1.这个题就能用。

是了，赞👍

不是只有0和-1才能正确赋值吗

嗯，是这样的

0的二进制是32个0，-1的二进制是32个1，只是说0和-1符合直观的按比特赋值定义，并不是说就不能赋其他值。对于这题，memset(g, -1, sizeof(g));的作用是将地图周围墙掉，防止越界，故第二个参数只要不是0就可以

不是0就够了吧，不需要再保证不是1。就算地图之外是1，也没法再越界访问了。

还可以赋值无穷

我觉得BFS只需要在找到结果就输出答案，然后结束就可以了

#### 爱惨海绵宝宝了

宝儿哥！牛逼

主函数那块为什么要从1开始读入g数组，我从0开始读入，然后bfs(0,0)没有输出

我也想问

因为它memset(g,1,sizeof g)这个等于说把g全部变成了墙，而它输入进g的数时i和j是从1开始的，等于说0这一行和列都变成了墙，所以不能从0,0开始

因为它memset(g,1,sizeof g)这个等于说把g全部变成了墙，而它输入进g的数时i和j是从1开始的，等于说0这一行和列都变成了墙，所以不能从0,0开始

入队的时候置为1了，不是说memset不是初始化为1吗？

为什么x和y不需要判断边界呢

memset把g【N][N]初始化了，所以边界都是1，然后memset后面又给m与n范围内赋值0，来确定路径。

她留了0作为边界 所以上下找不会越界

能更新下怎么输出路径吗求求了

####
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]

using namespace std;
typedef pair[HTML_REMOVED] PII;
const int N = 110;
int g[N][N];
int f[N][N];
int n, m;

void bfs(int a, int b) {
queue[HTML_REMOVED] q;
q.push({a, b});
while (!q.empty()) {
PII start = q.front();
q.pop();
g[start.first][start.second] = 1;
int dx[4]{1, 0, -1, 0}, dy[4]{0, -1, 0, 1};

    for (int i = 0; i < 4; i ++ ) {
        int x = dx[i] + start.first, y = dy[i] + start.second;
        if (g[x][y] == 0) {
            g[x][y] = 1;
            f[x][y] = 1 + f[start.first][start.second];
            q.push({x, y});
        }
    }

}
cout << f[n][m] <<endl;

}

void bfs_print() {
int target = f[n][m];
queue[HTML_REMOVED] q;
q.push({n, m});
cout << n << ” ” << m <<endl;
while (!q.empty()) {
PII start = q.front();
q.pop();

    int dx[4]{0, 1, 0, -1}, dy[4]{1, 0, -1, 0};
    for (int i = 0; i < 4; i ++ ) {
        int x = dx[i] + start.first, y = dy[i] + start.second;
        if ( x>=1 && y>=1 && x<=n && x<=m && f[x][y] == target -1 ) {
            q.push({x, y});
            cout << x << " " << y << endl;
        }

    }
        target--;
}

}

int main()
{
cin.tie(0);
memset(g, 1, sizeof (g));
cin >> n >> m;
for (int i = 1; i <= n; i ) {
for (int j = 1; j <= m; j ) {
cin >> g[i][j];
}
}

bfs(1, 1);
bfs_print();
return 0;

}

这代码不知道为什么超时了（为了防止我自己的问题，直接复制的）

你试试直接提交，别点调试

请问一下g[1][1]是怎么变成1的

我认为g[1][1]不是在被用完之后立马就变为1的 而是遍历g[1][2]的时候才将g[1][1]赋值为1的。这样有些数据可能会出错

memset(g, -1, sizeof(g));实在不明白这一步意思是在干嘛呀

后面不是要输入吗

为什么一开始要把g数组的值赋成一啊？

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
// #include <vector>

#define x first
#define y second

using namespace std;

typedef pair<int,int> PII;

const int N = 110;

int g[N][N];
int d[N][N];
int dx[4] = {-1,0,1,0},dy[4] = {0,1,0,-1};
int n,m;

// vector<PII> q;
PII q[N * N];

int dfs()
{
    int hh = 0,tt = 0;
    q[hh] = {0,0};
    memset(d,-1,sizeof d);
    d[0][0] = 0;

    while(hh <= tt)
    {
        PII t = q[hh];
        hh++;

        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 && g[x][y] == 0 && d[x][y] == -1)
            {
                d[x][y] = d[t.first][t.second] + 1;
                q[++tt] = {x,y};
            }
        }
    }

    return d[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",&g[i][j]);
        }
    }

    printf("%d\n",dfs());

    return 0;
}

为什么vector[HTML_REMOVED] q;就会报错
PII q[N * N];这样才可以啊，我不理解这个是为什么，原则上不都是可以的吗?

为什么起点一定要为（1，1）呢，换成（0，0）就超时了

因为它memset(g,1,sizeof g)这个等于说把g全部变成了墙，而它输入进g的数时i和j是从1开始的，等于说0这一行和列都变成了墙，所以不能从0,0开始

这种方法怎么在bfs函数里面添加打印路径