如何修正C++实现的BFS以解决Hackerrank BotClean问题

实现BotClean网格扫地机器人逻辑时出现异常：

• 当脏污格子位于机器人当前位置的相邻格时，程序可以正确输出移动/清理指令
• 当脏污格子和机器人距离超过1格时，程序完全无输出，无法正常工作

核心实现代码如下：

#include<iostream>
#include<vector>
#include <queue>

using namespace std;


// searches and checks if the coordinates are previously visited or not
bool search_(vector<vector<int>> check, vector<int> coords){
    
    int len = check.size();
    
    for(int i = 0; i < len; i++){
        if(check[i][0] == coords[0] && check[i][1] == coords[1]){
            return false;
        }
    }
    return true;
}

vector<int> bfs(vector<string> board, int r, int c, int n){
    
    queue<vector<int>> q;
    vector<int> initial, mt;
    initial.push_back(r);
    initial.push_back(c);
    
    mt.push_back(-1);
    mt.push_back(-1);    
    
    q.push(initial);
    
    vector<vector<int>> check_arr;
    if(search_(check_arr, initial)){
        check_arr.push_back(initial);
    }

    vector<int> last;
    vector<int> neighbour1, neighbour3;
    vector<int> neighbour2, neighbour4;
    int n1 = 0, n2 = 0, n3 = 0, n4 = 0;
    
    while(1){
        if(q.empty()){
            return mt;
        }
        
        last = q.back();
        q.pop();
        
        if(board[last[0]][last[1]] == 'd'){
            return last;
        }
        
        if(search_(check_arr, last)){
            check_arr.push_back(last);
        }
   
        
        // Neighbours
        n1 = 0; n2 = 0; n3 = 0; n4 = 0;
        neighbour1.push_back(last[0]);
        neighbour1.push_back(last[1]+1);
        
        
        if(last[1]+1 < n){
            n1 = 1;
        }
        
        if(board[neighbour1[0]][neighbour1[1]] == 'd' && search_(check_arr, neighbour1) && last[1]+1 < n){
            return neighbour1;
        }
        
        neighbour2.push_back(last[0]+1);
        neighbour2.push_back(last[1]);
        
        if(last[0]+1 < n){
            n2 = 1;
        }

        if(board[neighbour2[0]][neighbour2[1]] == 'd' && search_(check_arr, neighbour2) && last[0]+1 < n){
            return neighbour2;
        }
        
        neighbour3.push_back(last[0]);
        neighbour3.push_back(last[1]-1);
        
        if(last[1]-1 >= 0){
            n3 = 1;
        }
        
        if(board[neighbour3[0]][neighbour3[1]] == 'd' && search_(check_arr, neighbour3) && last[1]-1 >=0){
            return neighbour3;
        }
        
        neighbour4.push_back(last[0]-1);
        neighbour4.push_back(last[1]);
        
        if(last[0]-1 >= 0){
            n4 = 1;
        }

        if(board[neighbour4[0]][neighbour4[1]] == 'd' && search_(check_arr, neighbour4) && last[0]-1 >= 0){
            return neighbour4;
        }
        
        if(search_(check_arr, neighbour1) && n1 == 1){
            check_arr.push_back(neighbour1);
            q.push(neighbour1);
        }
        if(search_(check_arr, neighbour2) && n2 == 1){
            check_arr.push_back(neighbour2);
            q.push(neighbour2);
        }
        if(search_(check_arr, neighbour3) && n3 == 1){
            check_arr.push_back(neighbour3);
            q.push(neighbour3);
        }
        if(search_(check_arr, neighbour4) && n4 == 1){
            check_arr.push_back(neighbour4);
            q.push(neighbour4);
        }
        
        neighbour1.clear();
        neighbour2.clear();
        neighbour3.clear();
        neighbour4.clear();
        last.clear();
    }
    
    return mt;
}

void next_move(int posr, int posc, vector <string> board) {
    //add logic here
    
    // Use BFS to determine the closest dirty position
    vector<int> next_pos = bfs(board, posr, posc, board.size());
    
    // Move towards it
    if(next_pos[0] - posr > 0){
        cout<<"DOWN\n";
        return;
    }
    else{
        if(next_pos[0] != posr){
            cout<<"UP\n";
            return;
        }
    }
    
    if(next_pos[1] - posc > 0){
        cout<<"RIGHT\n";
        return;
    }
    else{
        if(next_pos[1] != posc){
            cout<<"LEFT\n";
            return;
        }
    }
    
    if(next_pos[0] == posr && next_pos[1] == posc){
        cout<<"CLEAN\n";
        return;
    }
}

int main(void) {
    int pos[2];
    vector <string> board;
    cin>>pos[0]>>pos[1];
    for(int i=0;i<5;i++) {
        string s;cin >> s;
        board.push_back(s);
    }
    next_move(pos[0], pos[1], board);
    return 0;
}

代码存在3个核心逻辑错误，前两个直接导致远距离场景下程序崩溃无输出：

1. 边界判断顺序错误，触发数组越界崩溃
   所有判断邻居是否为脏污格的if语句，都把边界合法性判断放在了最后。C++逻辑与运算按从左到右顺序执行、短路求值，意味着程序会先访问board[neighbourX[0]][neighbourX[1]]，再判断坐标是否在合法范围内。当搜索范围扩大到网格边界附近时，会直接访问越界内存触发段错误，程序直接退出，自然没有输出。相邻场景下机器人初始位置一般不在边界，邻居坐标全部合法，所以不会触发这个问题。
2. BFS队列操作逻辑错误，退化为DFS
   标准BFS是先进先出结构，需要取队首元素q.front()遍历，代码里错误使用q.back()取队尾元素，把队列当成栈用，完全丧失了按层遍历找最短路径的能力，还很容易陷入无效遍历。
3. 已访问标记逻辑冗余，性能极差
   search_函数使用值传递已访问数组，每次调用都会完整拷贝整个数组，网格稍微大一点性能就会急剧下降；同时节点出队时才重复判断是否已访问，存在重复入队的冗余问题。

按以下点修改即可正常运行：

• 所有涉及网格坐标访问的逻辑，先判断坐标是否在[0, n-1]范围内，再访问数组内容
• 把队列取元素的q.back()改为q.front()，保证BFS按层遍历，找到的第一个脏污格就是距离最近的
• 邻居节点在入队时就标记为已访问，避免重复入队
• search_函数参数改为const引用传递，避免不必要的数组拷贝

修复后的核心BFS逻辑参考：

// 改为引用传递，避免无意义拷贝
bool search_(const vector<vector<int>>& check, const vector<int>& coords){
    for(const auto& p : check){
        if(p[0] == coords[0] && p[1] == coords[1]){
            return false;
        }
    }
    return true;
}

vector<int> bfs(const vector<string>& board, int r, int c, int n){
    queue<vector<int>> q;
    const vector<int> mt = {-1,-1};
    vector<vector<int>> visited;
    // 统一定义四个方向，减少冗余代码
    const int dirs[4][2] = {{-1,0}, {1,0}, {0,-1}, {0,1}};

    q.push({r,c});
    visited.push_back({r,c});

    while(!q.empty()){
        // 取队首元素，遵循BFS先进先出规则
        vector<int> curr = q.front();
        q.pop();

        if(board[curr[0]][curr[1]] == 'd'){
            return curr;
        }

        for(auto& dir : dirs){
            int nr = curr[0] + dir[0];
            int nc = curr[1] + dir[1];
            // 先判断边界合法性，再做后续操作，从根源杜绝越界
            if(nr >=0 && nr <n && nc >=0 && nc <n){
                vector<int> next = {nr, nc};
                if(search_(visited, next)){
                    visited.push_back(next);
                    q.push(next);
                }
            }
        }
    }
    return mt;
}

内容的提问来源于stack exchange，提问作者CED19I027 NIMMAGADDA SREE DHYU