如何纠正我的广度第一次搜索？

Question

我一直在尝试解决以下AI问题：

https://wwww.hackerrank.com/挑战/植物学/问题

这是我的代码：

#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;
}

基本上，我能够正确地识别我的邻居是否肮脏。但这并不能超出该范围。 请帮助我在这里。我认为我在BFS的某个地方错了。 当肮脏的位是我的机器人的邻居时，答案是正确的。但是，如果不是，答案根本不会打印。 谢谢。

Answer 1

我发现我的错误
我在这条线附近遇到了一个细分错误：

'''
    if(board[neighbour3[0]][neighbour3[1]] == 'd' && search_(check_arr, neighbour3) && last[1]-1 >=0){
        return neighbour3;
'''

原因是neighbour3不是邻居。
因此，编译器无法检查条件板[neighbour3 [0]] [neighbour3 [1]] =='d'，并且显示了分割错误。
我将其更改为：

    '''
    if(last[1]-1 >=0 && board[neighbour3[0]][neighbour3[1]] == 'd' && search_(check_arr, neighbour3)){
        return neighbour3;
'''

然后它正常工作:)

Answer 2

我现在没有太长的时间来处理您的代码，但是我相信这可能与您调用的每次迭代的迭代有关。

last = q.back();
q.pop();

如果您检查 STD的C ++文档q.push（...）将项目推到队列的 front ，q.last（）访问 last 在队列中的项目，q.pop（）从队列的 front 中弹出项目。这在您的代码中是有问题的，因为在每次迭代中，您都在弹出可能尚未检查的项目。为您的BFS执行此操作的正确方法是

toCheck = q.pop();

，然后在每个循环中检查tocheck变量。希望这有帮助！