Hello, I am trying to implement the C++ problem below using breadth first search

Question

Hello, I am trying to implement the C++ problem below using breadth first search and the included framework. Any help is appreciated. Thanks!

--------------------

"Hike on a Graph" is played on a board on which an undirected graph with colored edges. The graph is complete and has all loops; for any two locations there is exactly one edge (arrow) between them. The arrows are colored. There are three players, and each of them has a piece. At the beginning of the game, the three pieces are in fixed locations on the graph. In turn, the players move their pieces. A move consists of moving one's own piece along an arrow to a new location on the board. The following constraint is imposed on this: the piece may only be moved along arrows of the same color as the arrow between the two opponents' pieces.

In the sixties a one-person variant of the game emerged. In this variant one person moves all the three pieces, not necessarily one after the other, but of course only one at a time. Goal of this game is to get all pieces onto the same location, using as few moves as possible. Find out the smallest number of moves that is necessary to get all three pieces onto the same location, for a given board layout and starting positions.

Input Specification:

The input file contains several test cases. Each test case starts with the number n. Input is terminated by n=0. Otherwise, 1<=n<=50. Then follow three integers p1, p2, p3 with 1<=pi<=n denoting the starting locations of the game pieces. The colors of the arrows are given next as a m×m matrix of whitespace-separated lower-case letters. The element mij denotes the colour of the arrow between the locations i and j. Since the graph is undirected, you can assume the matrix to be symmetrical.

Output Specification:

For each test case output on a single line the minimum number of moves required to get all three pieces onto the same location, or the word "impossible" if that is not possible for the given board and starting locations.

---------------------

class Node
{
   public:
       //node identifier, anything (preferably unique)
       string name;
       //create the resulting path
       Node* parent = NULL;
       //all nodes reachable by the current
       vector neighbors;
       Node(string);
      
       void addNeighbors(vector);
       void addNeighbor(Node*);
};

Node::Node(string n)
{
   name = n;
}

void Node::addNeighbors(vector nodes)
{
   for(int i=0;i    {
       addNeighbor(nodes[i]);
   }

}

void Node::addNeighbor(Node* node)
{
   neighbors.push_back(node);
}

void breadthFirst (int n, int p1, int p2, int p3)
{
   queue nodes;
   unordered_map examined;
   Node init_node("Name");
   nodes.push(&init_node);
   examined[init_node.name] = true;
  
   //BFS! (Queue Traversal)
   while(!nodes.empty())
   {
       //dequeue a vertex from queue
       Node* currNode = nodes.front();
       nodes.pop();
       //Get adjacent verticies of dequeued vertex
       for(int i = 0; ineighbors.size(); i++)
       {
       //check to make sure point hasn't been looked at
           if(examined.find(currNode->neighbors[i]->name) == examined.end())
           {
               examined[currNode->neighbors[i]->name] = true;
               //set the parent to the curr node
               currNode->neighbors[i]->parent = currNode;
               //add neighbor to the queue
               nodes.push(currNode->neighbors[i]);
           }
       }
   }
}

Explanation / Answer

import java . util . ArrayList ;
import java . util . PriorityQueue ;
public class BST_Graph
{
public static void main(String [ ] args)
{

PriorityQueue < Node > queue = new PriorityQueue <>();

HashMap < Node , Boolean > visited = new HashMap <> ();
Node init node = new Node("Name");
queue . add(init node);
visited . put ( init node , True);

while (! queue . isEmpty ())
{
Node curr node = queue . poll ( ) ;
for ( Node next node : curr node . neighbors)
{
if
(! visited . contains(next node))
{
visited . put (next node , True);
next node . parent = curr node ;
queue . add( next node )
}
}
}

}

public static class Node
{
public final String name;
public Node parent = null;
public final ArrayList < Node > neighbors = new ArrayList <> ();
public Node(String name)
{
this .name = name;
}
public void addNeighbors ( ArrayList < Node > nodes)
{
neighbors . addAll (nodes);
}
}
}

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.