HackerRank: PacMan - BFS

HackerRank: PacMan - BFS

In the previous game, you performed DFS on the PacMan grid. It was seen that DFS might not always give the shortest path between the source and the destination.

In this game, PacMan is positioned in a grid. PacMan has to find the food using Breadth First Search (BFS), provided the grid is completely observable, perform a BFS on the grid and then print the path obtained by BFS from the PacMan to the food.

static void nextMove(){
_queue.add(Pacman);
while (!_found){
Visit(_queue.pollFirst());
}
}
static void Visit(Position p){
if (Grid[p.Abs][p.Ord] == '%') return;
if (VisitedNodes[p.Abs][p.Ord]) return;

_numVisitedNodes++;
_visit.addLast(p);

VisitedNodes[p.Abs][p.Ord] = true;

if (Grid[p.Abs][p.Ord] == '.') {
_found = true;
p.BuildPath(_path);
_length = _path.size() - 1;
}

p.Visit(_queue);
}
public void Visit(LinkedList<Position> queue){
if (Abs != 0 && !Solution.VisitedNodes[Abs-1][Ord])
queue.addLast(new Position(Abs - 1, Ord, this));

if (Ord != 0 && !Solution.VisitedNodes[Abs][Ord-1])
queue.addLast(new Position(Abs, Ord - 1, this));

if (Ord != Solution.numCol - 1 && !Solution.VisitedNodes[Abs][Ord+1])
queue.addLast(new Position(Abs, Ord + 1, this));

if (Abs != Solution.numRows - 1 && !Solution.VisitedNodes[Abs+1][Ord])
queue.addLast(new Position(Abs + 1, Ord, this));
}

class Node {
    public int x;
    public int y;
    public Node prev_node;
    public boolean visited;
}