bfs写错了，请帮助修改

Question

本意是看是否能从vis[0][0]走到vis[12][12]
但无论输入什么，都输出no。我看不出错误

#include<bits/stdc++.h>
using namespace std;
bool bfs(){
    queue<pair<int,int> > q;
    bool vis[13][13];
    for(int i=0;i<13;i++)
    {
        for(int j=0;j<13;j++)
        {
            cin>>vis[i][j];
        }
    }
    q.push(make_pair(0,0));
    while(!q.empty())
    {
        pair<int,int> zb=q.front();
        if(vis[zb.first+1][zb.second]){
            q.push(make_pair(zb.first+1,zb.second));
            vis[zb.first+1][zb.second]=1;
        }
            
        if(vis[zb.first-1][zb.second]){
            q.push(make_pair(zb.first-1,zb.second));
            vis[zb.first-1][zb.second]=1;
        }
            
        if(vis[zb.first][zb.second+1]){
            q.push(make_pair(zb.first,zb.second+1));
            vis[zb.first][zb.second+1]=1;
        }
            
        if(vis[zb.first][zb.second-1]){
            q.push(make_pair(zb.first,zb.second-1));
            vis[zb.first][zb.second-1]=1;
        }
            
        q.pop();
    }
    if(vis[12][12]==0)return false;
    else return true;
}
int main(){
    if(bfs())cout<<"yes";
    else cout<<"no";
}

Answer 1

引自免费微信小程序：皆我百晓生

看起来你的bfs代码逻辑存在一些错误。你的代码主要问题在于，当在队列中查找下一个位置时，你正在检查目标位置是否已经被访问过（标记为vis），然后尝试在队列中添加这个位置。然而，你没有正确地检查所有相邻的位置是否可达，并且没有正确地更新队列中的位置。此外，当你从队列中取出一个位置并试图在四个方向上移动时，你需要先确认那个位置在数组的边界内。否则，如果你试图访问数组边界之外的位置，你的程序可能会出现错误或异常。以下是你的代码的修正版本：

#include<bits/stdc++.h>
using namespace std;

bool bfs() {
    queue<pair<int, int>> q;
    bool vis[13][13];
    memset(vis, 0, sizeof(vis)); // 将vis数组初始化为全零
    for(int i=0; i<13; i++) {
        for(int j=0; j<13; j++) {
            cin >> vis[i][j]; // 输入每个位置的访问状态
        }
    }
    q.push({0, 0}); // 将起始点放入队列中
    vis[0][0] = true; // 将起始点标记为已访问
    while(!q.empty()) {
        pair<int, int> zb = q.front(); // 获取队列中的第一个元素
        q.pop(); // 从队列中移除第一个元素
        // 检查四个方向的相邻位置是否可达且未被访问过，并添加到队列中
        if((zb.first + 1 < 13 && vis[zb.first + 1][zb.second] == 0) && !vis[zb.first + 1][zb.second]) { // 右移
            q.push({zb.first + 1, zb.second});
            vis[zb.first + 1][zb.second] = true; // 标记为已访问
        }
        if((zb.first - 1 >= 0 && vis[zb.first - 1][zb.second] == 0) && !vis[zb.first - 1][zb.second]) { // 左移
            q.push({zb.first - 1, zb.second});
            vis[zb.first - 1][zb.second] = true; // 标记为已访问
        }
        if((zb.second + 1 < 13 && vis[zb.first][zb.second + 1] == 0) && !vis[zb.first][zb.second + 1]) { // 下移
            q.push({zb.first, zb.second + 1});
            vis[zb.first][zb.second + 1] = true; // 标记为已访问
        }
        if((zb.second - 1 >= 0 && vis[zb.first][zb.second - 1] == 0) && !vis[zb.first][zb.second - 1]) { // 上移
            q.push({zb.first, zb.second - 1});
            vis[zb.first][zb.second - 1] = true; // 标记为已访问
        }
    }
    return vis[12][12]; // 返回目标位置是否被访问过（是否可达）的状态值（true或false）
}
int main() {
    if(bfs()) cout << "yes"; // 如果bfs函数返回true，则输出"yes"表示可达目标位置
    else cout << "no"; // 如果bfs函数返回false，则输出"no"表示无法到达目标位置
}

这个修正版本的代码应该能够解决你的问题。现在，它应该能正确地执行宽度优先搜索（BFS），并判断是否能从起点到达目标位置。希望这能帮助到你！