Search code examples
c++breadth-first-searchshortest-path

Problem: Shortest path in a grid between multiple point with a constraint

Problem description:

enter image description here

I'm trying to solve a problem on the internet and I wasn't able to pass all testcases, well, because my logic is flawed and incorrect. The flaw: I assumed starting to the closest 'F' point will get me to the shortest paths always, at all cases.

Thinks I thought of:

  • Turning this into a graph problem and solve it based on it. > don't think this would work because of the constraint?
  • Try to obtain all possible solution combinations > does not scale, if !8 combination exist.
#include <iostream>
#include <utility> 
#include <string>
#include <vector>
#include <queue>
using namespace std;

#define N 4
#define M 4

int SearchingChallenge(string strArr[], int arrLength) {
  int  n = arrLength, m = n, steps = 0, food = 0;
  // initial position of charlie
  int init_j = 0;
  int init_i = 0;
  queue<pair<int,int>> q;
  // directions
  vector<int> offsets = {0,-1,0,1,0};
  vector<pair<int,int>> food_nodes;
  //store visited nodes, no need for extra work to be done.
  int visited_nodes[4][4] = {{0}};
  
  // get number of food pieces 
  for(int i = 0; i < m; i++){
    for(int j = 0; j < n ; j++){
      if(strArr[i][j] == 'F')
      {
          food++;
      }
      if(strArr[i][j] == 'C')
      {
        strArr[i][j] = 'O';
        food_nodes.push_back({i,j});
      }
    }
  }
  while(food_nodes.size()>0){
      food_nodes.erase(food_nodes.begin());
      int break_flag=0;
      q.push(food_nodes[0]);
  while(!q.empty()){
      int size = q.size();
      while(size-->0){
      pair<int,int> p = q.front();
      q.pop();
      for(int k = 0; k < 4; k++){
      int ii = p.first + offsets[k], jj = p.second + offsets[k+1];
    /*  if(ii == 0 && jj == 3)
        printf("HI"); */
      if(jj >= 0 && jj < 4 && ii < 4 && ii >=0){
          if(strArr[ii][jj] == 'F'){
             strArr[ii][jj] = 'O';
            while(!q.empty())
                q.pop();
            break_flag=1;
            food--;
            food_nodes.push_back({ii,jj});
            break;
          }
          if(strArr[ii][jj] == 'O')
            q.push({ii,jj});
            
            
            if(strArr[ii][jj] == 'H' && food == 0)
                return ++steps;
        }   
     }
    if(break_flag==1)
        break;
    }
    steps++;
    if(break_flag==1)
        break;
  }
}
  return 0;
}

int main(void) { 
   
  // keep this function call here
  /* Note: In C++ you first have to initialize an array and set 
     it equal to the stdin to test your code with arrays. */

  //passing testcase
  //string A[4] = {"OOOO", "OOFF", "OCHO", "OFOO"};
  //failing testcase
  string A[4] = {"FOOF", "OCOO", "OOOH", "FOOO"}
  int arrLength = sizeof(A) / sizeof(*A);
  cout << SearchingChallenge(A, arrLength);
  return 0;
    
}

Your help is appreciated.

Solution

  • You can write a DP solution where you have a 4x4x8 grid. The first two axis represent the x and y coordinate. The third one represent the binary encoding of which food item you picked already.

    Each cell in the grid stores the best number of moves to get at this cell having eaten the specified foods. So for example, grid[2][2][2] is the cost of getting to cell (2,2) after having eaten the second piece of food only.

    Then you set the value of the start cell, at third index 0 to 0, all the other cells to -1. You keep a list of the cells to propagate (sorted by least cost), and you add the start cell to it.

    Then you repeatedly take the next cell to propagate, remove it and push the neighboring cell with cost +1 and updated food consume. Once you reach the destination cell with all food consumed, you're done.

    That should take no more than 4x4x8 updates, with about the same order of priority queue insertion. O(n log(n)) where n is xy2^f. As long as you have few food items this will be almost instant.