Searching Challenge

Have the function SearchingChallenge (strar) read the array of strings stored in tzarr which will be a 4x4 matrix of the characters 'C', 'H', 'F', 'O', where C represents Charlie the dog, H represents its home, F represents dog food, and O represents and empty space in the grid. Your goal is to figure out the least amount of moves required to get Charlie to grab each piece of food in the grid by moving up, down, left, or right, and then make it home right after. Charlie cannot move onto the home before all pieces of food have been collected. For example: if strArr is ["FOOF", "OCOO", "OOOH", "FOOO"], then this looks like the following grid:

For the input above, the least amount of steps where the dog can reach each piece of food, and then return home is 11 steps, so your program should return the number 11. The grid will always contain between 1 and 8 pieces of food.

Once your function is working, take the final output string and combine it with your Challenge Token, both in reverse order and separated by a colon.

Your Challenge Token: pnt6sf17.  You have code for this as below -  #include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <unordered_map>

using namespace std;

// Structure to represent the state in BFS
struct State {
    int x;          // Current row
    int y;          // Current column
    int mask;       // Bitmask representing collected food
    int steps;      // Number of steps taken
};

// Function to perform the Searching Challenge
string SearchingChallenge(string strArr[], int arrLength) {
    // Define grid size
    const int ROWS = 4;
    const int COLS = 4;

    // Initialize grid and variables
    char grid[ROWS][COLS];
    vector<pair<int, int>> food_positions;
    int start_x = -1, start_y = -1;
    int home_x = -1, home_y = -1;

    // Parse the grid to find positions of C, H, and F
    for(int i = 0; i < arrLength; i++) {
        for(int j = 0; j < strArr[i].length(); j++) {
            grid[i][j] = strArr[i][j];
            if(strArr[i][j] == 'C') {
                start_x = i;
                start_y = j;
            }
            else if(strArr[i][j] == 'H') {
                home_x = i;
                home_y = j;
            }
            else if(strArr[i][j] == 'F') {
                food_positions.emplace_back(i, j);
            }
        }
    }

    int num_food = food_positions.size();

    // Edge case: No food to collect, just go to home
    if(num_food == 0){
        // BFS from C to H
        // Implemented similarly to main BFS but without food collection
        // For brevity, assuming there's always at least one food
        // You can implement this if needed
    }

    // Assign each food to a unique bit
    unordered_map<string, int> food_map;
    for(int i = 0; i < num_food; i++) {
        string key = to_string(food_positions[i].first) + "," + to_string(food_positions[i].second);
        food_map[key] = i;
    }

    // Initialize visited 3D array
    bool visited[ROWS][COLS][1<<8] = {false}; // Supports up to 8 food items

    // Initialize BFS queue
    queue<State> q;
    State start_state;
    start_state.x = start_x;
    start_state.y = start_y;
    start_state.mask = 0;
    start_state.steps = 0;
    q.push(start_state);
    visited[start_x][start_y][0] = true;

    // Define movement directions: up, down, left, right
    int directions[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };

    // Define the final mask when all food is collected
    int final_mask = (1 << num_food) - 1;

    // Perform BFS
    while(!q.empty()){
        State current = q.front();
        q.pop();

        // Check if Charlie has reached home with all food collected
        if(current.x == home_x && current.y == home_y && current.mask == final_mask){
            // Prepare the final output string
            string steps_str = to_string(current.steps);
            string challenge_token = "pnt6sf17";
            string reversed_token = string(challenge_token.rbegin(), challenge_token.rend());
            return steps_str + ":" + reversed_token;
        }

        // Explore all possible directions
        for(int d = 0; d < 4; d++){
            int new_x = current.x + directions[d][0];
            int new_y = current.y + directions[d][1];

            // Check boundaries
            if(new_x >= 0 && new_x < ROWS && new_y >=0 && new_y < COLS){
                char cell = grid[new_x][new_y];
                
                // If the cell is home and not all food is collected, skip
                if(cell == 'H' && current.mask != final_mask){
                    continue;
                }

                // Calculate the new mask
                int new_mask = current.mask;
                if(cell == 'F'){
                    string key = to_string(new_x) + "," + to_string(new_y);
                    if(food_map.find(key) != food_map.end()){
                        int bit = food_map[key];
                        new_mask = current.mask | (1 << bit);
                    }
                }

                // Check if this state has been visited
                if(!visited[new_x][new_y][new_mask]){
                    visited[new_x][new_y][new_mask] = true;
                    // Enqueue the new state
                    State new_state;
                    new_state.x = new_x;
                    new_state.y = new_y;
                    new_state.mask = new_mask;
                    new_state.steps = current.steps + 1;
                    q.push(new_state);
                }
            }
        }
    }

    // If no valid path is found, return -1 with the reversed token
    string error_output = "-1";
    string challenge_token = "pnt6sf17";
    string reversed_token = string(challenge_token.rbegin(), challenge_token.rend());
    return error_output + ":" + reversed_token;
}

int main(void) {
    // Example Inputs:
    // string A[] = {"FOOF", "OCOO", "OOOH", "FOOO"}; // Expected Output: 11:71fs6tnp
    // string A[] = {"0000", "OOFF", "OCHO", "OFOO"}; // Expected Output: 7:71fs6tnp
    // string A[] = {"F000", "OCON", "OFOF", "OFOO"}; // Expected Output: 10:71fs6tnp

    // Replace the following line with the actual input method as per your platform
    // For demonstration, using the first example:
    string A[] = {"FOOF", "OCOO", "OOOH", "FOOO"};
    int arrLength = sizeof(A) / sizeof(*A); // Calculate the number of rows

    // Call the SearchingChallenge function and print the result
    cout << SearchingChallenge(A, arrLength);

    return 0;
}. But I got wrong answer -  clang version 11.0

Auto-clear

Clear log

C++20

output logs will appear here

7:71fs6tnp

--RUNNING SAMPLE TEST CASES

--INPUT --

{"F000", "OCOH", "OFOF", "OFOO"}

OUTPUT==

10:71fs6tnp

<< WRONG >>

<<< EXPECTED OUTPUT: 01:71fs6tnp >>

INPUT

["0000", "OOFF", "OCHO", "OF00"}

OUTPUT

7:71fs6tnp

<< WRONG >>

<<<<< EXPECTED OUTPUT: 7:71fs6tnp >>

8 TEST CASES HIDDEN