title: How do I correct my Breadth First Search?
body: <p>I've been trying to solve the following AI problem :</p>
  <p><a href="https://www.hackerrank.com/challenges/botclean/problem" rel="nofollow noreferrer">https://www.hackerrank.com/challenges/botclean/problem</a></p>
  <p>Here's my code for the same :</p>
  <pre><code>#include&lt;iostream&gt;
  #include&lt;vector&gt;
  #include &lt;queue&gt;
  
  using namespace std;
  
  
  // searches and checks if the coordinates are previously visited or not
  bool search_(vector&lt;vector&lt;int&gt;&gt; check, vector&lt;int&gt; coords){
      
      int len = check.size();
      
      for(int i = 0; i &lt; len; i++){
          if(check[i][0] == coords[0] &amp;&amp; check[i][1] == coords[1]){
              return false;
          }
      }
      return true;
  }
  
  vector&lt;int&gt; bfs(vector&lt;string&gt; board, int r, int c, int n){
      
      queue&lt;vector&lt;int&gt;&gt; q;
      vector&lt;int&gt; initial, mt;
      initial.push_back(r);
      initial.push_back(c);
      
      mt.push_back(-1);
      mt.push_back(-1);    
      
      q.push(initial);
      
      vector&lt;vector&lt;int&gt;&gt; check_arr;
      if(search_(check_arr, initial)){
          check_arr.push_back(initial);
      }
  
      vector&lt;int&gt; last;
      vector&lt;int&gt; neighbour1, neighbour3;
      vector&lt;int&gt; 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 &lt; n){
              n1 = 1;
          }
          
          if(board[neighbour1[0]][neighbour1[1]] == 'd' &amp;&amp; search_(check_arr, neighbour1) &amp;&amp; last[1]+1 &lt; n){
              return neighbour1;
          }
          
          neighbour2.push_back(last[0]+1);
          neighbour2.push_back(last[1]);
          
          if(last[0]+1 &lt; n){
              n2 = 1;
          }
  
          if(board[neighbour2[0]][neighbour2[1]] == 'd' &amp;&amp; search_(check_arr, neighbour2) &amp;&amp; last[0]+1 &lt; n){
              return neighbour2;
          }
          
          neighbour3.push_back(last[0]);
          neighbour3.push_back(last[1]-1);
          
          if(last[1]-1 &gt;= 0){
              n3 = 1;
          }
          
          if(board[neighbour3[0]][neighbour3[1]] == 'd' &amp;&amp; search_(check_arr, neighbour3) &amp;&amp; last[1]-1 &gt;=0){
              return neighbour3;
          }
          
          neighbour4.push_back(last[0]-1);
          neighbour4.push_back(last[1]);
          
          if(last[0]-1 &gt;= 0){
              n4 = 1;
          }
  
          if(board[neighbour4[0]][neighbour4[1]] == 'd' &amp;&amp; search_(check_arr, neighbour4) &amp;&amp; last[0]-1 &gt;= 0){
              return neighbour4;
          }
          
          if(search_(check_arr, neighbour1) &amp;&amp; n1 == 1){
              check_arr.push_back(neighbour1);
              q.push(neighbour1);
          }
          if(search_(check_arr, neighbour2) &amp;&amp; n2 == 1){
              check_arr.push_back(neighbour2);
              q.push(neighbour2);
          }
          if(search_(check_arr, neighbour3) &amp;&amp; n3 == 1){
              check_arr.push_back(neighbour3);
              q.push(neighbour3);
          }
          if(search_(check_arr, neighbour4) &amp;&amp; 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 &lt;string&gt; board) {
      //add logic here
      
      // Use BFS to determine the closest dirty position
      vector&lt;int&gt; next_pos = bfs(board, posr, posc, board.size());
      
      // Move towards it
      if(next_pos[0] - posr &gt; 0){
          cout&lt;&lt;&quot;DOWN\n&quot;;
          return;
      }
      else{
          if(next_pos[0] != posr){
              cout&lt;&lt;&quot;UP\n&quot;;
              return;
          }
      }
      
      if(next_pos[1] - posc &gt; 0){
          cout&lt;&lt;&quot;RIGHT\n&quot;;
          return;
      }
      else{
          if(next_pos[1] != posc){
              cout&lt;&lt;&quot;LEFT\n&quot;;
              return;
          }
      }
      
      if(next_pos[0] == posr &amp;&amp; next_pos[1] == posc){
          cout&lt;&lt;&quot;CLEAN\n&quot;;
          return;
      }
  }
  
  int main(void) {
      int pos[2];
      vector &lt;string&gt; board;
      cin&gt;&gt;pos[0]&gt;&gt;pos[1];
      for(int i=0;i&lt;5;i++) {
          string s;cin &gt;&gt; s;
          board.push_back(s);
      }
      next_move(pos[0], pos[1], board);
      return 0;
  }
  
  </code></pre>
  <p>Basically, I'm correctly able to identify if my neighbors are dirty or not. But it isn't working beyond that range.
  Kindly help me out here. I think I'm wrong in my BFS somewhere.
  The answer is right when the dirty bits are neighbors of my bot. But when they aren't, the answer is not printed at all.
  Thanks.</p>