HackerRank: PacMan - DFS

HackerRank: PacMan - DFS

AI has a lot of problems that involves searches. In this track you will learn most of the search techniques used in AI.

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

https://codepair.hackerrank.com/paper/ppOnHL9O?b=eyJyb2xlIjoiY2FuZGlkYXRlIiwibmFtZSI6ImplZmZlcnl5dWFuIiwiZW1haWwiOiJ5dWFueXVuLmtlbm55QGdtYWlsLmNvbSJ9
static LinkedList<Position> _path;
static LinkedList<Position> _visit;

static void nextMove() {
DFS(Pacman.x, Pacman.y, 0);
}

static boolean DFS(int x, int y, int length) {
if (Grid[x][y] == '%')
return false;

_numVisitedNodes++;
_visit.addLast(new Position(x, y));
VisitedNodes[x][y] = true;

if (Grid[x][y] == '.') {
_path.addFirst(new Position(x, y));
_length = length;
return true;
}

if (x != numRows - 1 && !VisitedNodes[x + 1][y]) {
if (DFS(x + 1, y, length + 1)) {
_path.addFirst(new Position(x, y));
return true;
}
}

if (y != numCol - 1 && !VisitedNodes[x][y + 1]) {
if (DFS(x, y + 1, length + 1)) {
_path.addFirst(new Position(x, y));
return true;
}
}

if (y != 0 && !VisitedNodes[x][y - 1]) {
if (DFS(x, y - 1, length + 1)) {
_path.addFirst(new Position(x, y));
return true;
}
}

if (x != 0 && !VisitedNodes[x - 1][y]) {
if (DFS(x - 1, y, length + 1)) {
_path.addFirst(new Position(x, y));
return true;
}
}

return false;
}