#Solution

Solution

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;
       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. 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>>

   std::queue<std::pair<node*, size_t>> jumpQueue;
   jumpQueue.push(std::make_pair(houses[start].get(), 0));
   

   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.first-> houseLinks) {
           if (!visited[newHouse->houseID]) {
               visited[newHouse->houseID] = true;
               jumpQueue.push(std::make_pair(newHouse, oldHouse.second+1));
           }
           if (newHouse->houseID == end) {
               result = oldHouse.second+1;
               std::queue<std::pair<node*, size_t>> 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:

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

struct node {
    unsigned houseID;
    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<std::pair<node*, size_t>> jumpQueue;
    jumpQueue.push(std::make_pair(houses[start].get(), 0));

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

    std::cout << result << "\n";
}

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:

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

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;
       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. 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>>

   std::queue<std::pair<node*, size_t>> jumpQueue;
   jumpQueue.push(std::make_pair(houses[start].get(), 0));
   

   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.first-> houseLinks) {
           if (!visited[newHouse->houseID]) {
               visited[newHouse->houseID] = true;
               jumpQueue.push(std::make_pair(newHouse, oldHouse.second+1));
           }
           if (newHouse->houseID == end) {
               result = oldHouse.second+1;
               std::queue<std::pair<node*, size_t>> swapQueue;
               std::swap(swapQueue, jumpQueue);
           }
       }
   }
   

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

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;
       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. 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>>

   std::queue<std::pair<node*, size_t>> jumpQueue;
   jumpQueue.push(std::make_pair(houses[start].get(), 0));
   

   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.first-> houseLinks) {
           if (!visited[newHouse->houseID]) {
               visited[newHouse->houseID] = true;
               jumpQueue.push(std::make_pair(newHouse, oldHouse.second+1));
           }
           if (newHouse->houseID == end) {
               result = oldHouse.second+1;
               std::queue<std::pair<node*, size_t>> 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: