Skip to main content
4 of 4
Commonmark migration
  1. I think you choice of a data table is really bad. You should consider creating nodes similar to an trie.

    struct node {
        unsigned houseID;
        unsigned firstVisited = 0;
        std::vector<node*> houseLinks;
        explicit node(unsigned id) : houseID(id) {}
    };
    

    Then your initial code would look like this:

    unsigned numHouses, numLinks;
    std::cin >> numHouses >> numLinks;
    
    std::vector<std::unique_ptr<node>> houses;
    for (unsigned house = 0; house < numHouses; ++house) {
        houses.push_back(std::make_unique<node>(house));
    }
    

    I have to say, that my compiler hat home complains about make_unique. In any case this should work too houses.push_back(std::unique_ptr<node>(new node (house)));

  2. Now you have to add the links between the houses

    for (unsigned link = 0; link < numLinks; ++link) {
        unsigned house1, house2;
        std::cin >> house1 >> house2;            
        houses[house1-1]->houseLinks.push_back(houses[house2-1].get());
        houses[house2-1]->houseLinks.push_back(houses[house1-1].get());
    }
    
  3. Your checking part seems right, although i would suggest to group everything as it belongs:

    unsigned start, end;
    std::cin >> start >> end;
    start--;end--;
    
    std::vector<bool> visited(numHouses, false);
    visited[start] = true;
    
  4. EDIT: this is no longer relevant but i dont know how to cross it out. However, i would suggest, that you keep track of your jump length via the queue. So rather than haveing a queue<node*> have a queue<std::pair<node*, size_t>> New: I would now suggest to store the first visited field in the struct itself, which simplifies the code a lot

    std::queue<node*> jumpQueue;
    jumpQueue.push(houses[start].get());
    

    Now while you are adding something to the queue you just increment the jump index.

  5. Now to your breadth first search. Obviously you can ignore any occurrence of a house that was reached before, as that would lead to an at least equally large jumping series.

    size_t result = 0;
    while (!jumpQueue.empty()) {
        auto oldHouse = jumpQueue.front();
        jumpQueue.pop();
        for (auto newHouse : oldHouse->houseLinks) {
            if (!visited[newHouse->houseID]) {
                visited[newHouse->houseID] = true;
                newHouse->firstVisited = oldHouse->firstVisited+1;
                jumpQueue.push(newHouse);
            }
            if (newHouse->houseID == end) {
                result = oldHouse->firstVisited+1;
                std::queue<node*> swapQueue;
                std::swap(swapQueue, jumpQueue);
            }
        }
    }
    

    Note, that one can directly terminate the traversal of the trie by swapping the current queue with an empty one.

  6. Finally now that you have the result, or 0 if you never found the villan then print result. All together you now have:

Solution

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

struct node {
    unsigned houseID;
    unsigned firstVisited = 0;
    std::vector<node*> houseLinks;
    explicit node(unsigned id) : houseID(id) {}
};

int main()
{
    unsigned numHouses, numLinks;
    std::cin >> numHouses >> numLinks;

    std::vector<std::unique_ptr<node>> houses;
    for (unsigned house = 0; house < numHouses; ++house) {
        houses.push_back(std::unique_ptr<node>(new node (house)));
    }

    for (unsigned link = 0; link < numLinks; ++link) {
        unsigned house1, house2;
        std::cin >> house1 >> house2;
        houses[house1-1]->houseLinks.push_back(houses[house2-1].get());
        houses[house2-1]->houseLinks.push_back(houses[house1-1].get());
    }

    unsigned start, end;
    std::cin >> start >> end;
    start--;end--;

    std::vector<bool> visited(numHouses, false);
    visited[start] = true;

    std::queue<node*> jumpQueue;
    jumpQueue.push(houses[start].get());

    size_t result = 0;
    while (!jumpQueue.empty()) {
        auto oldHouse = jumpQueue.front();
        jumpQueue.pop();
        for (auto newHouse : oldHouse->houseLinks) {
            if (!visited[newHouse->houseID]) {
                visited[newHouse->houseID] = true;
                newHouse->firstVisited = oldHouse->firstVisited+1; 
                jumpQueue.push(newHouse);
            }
            if (newHouse->houseID == end) {
                result = oldHouse->firstVisited+1;
                std::queue<node*> swapQueue;
                std::swap(swapQueue, jumpQueue);
            }
        }
    }

    std::cout << result << "\n";
}
miscco
  • 4.3k
  • 11
  • 17