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)));
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()); }
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;
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 aqueue<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 lotstd::queue<node*> jumpQueue; jumpQueue.push(houses[start].get());
Now while you are adding something to the queue you just increment the jump index.
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.
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";
}