Given an N-by-N maze (like the one created in the previous exercise), write a pr

Question

Given an N-by-N maze (like the one created in the previous exercise), write a program to find a path from the start cell (1, 1) to the finish cell (N, N), if it exists. To find a solution to the maze, run the following algorithm, starting from (1, 1) and stopping if we reach cell (N, N).

explore(x, y)

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

- Mark the current cell (x, y) as "visited."

- If no wall to north and unvisited, then explore(x, y+1).

- If no wall to east and unvisited, then explore(x+1, y).

- If no wall to south and unvisited, then explore(x, y-1).

- If no wall to west and unvisited, then explore(x-1, y).

Java typed out please! comment each line

Explanation / Answer

// solve the maze using depth-first search
private void explore(int x, int y) {
if (x == 0 || y == 0 || x == n+1 || y == n+1) return;
if (done || visited[x][y]) return;
visited[x][y] = true;

// reached middle
if (x == n/2 && y == n/2) done = true;

if (!north[x][y]) explore(x, y + 1);
if (!east[x][y]) explore(x + 1, y);
if (!south[x][y]) explore(x, y - 1);
if (!west[x][y]) explore(x - 1, y);

if (done) return;
}

// solve the maze starting from the start state
public void explore() {
for (int x = 1; x <= n; x++)
for (int y = 1; y <= n; y++)
visited[x][y] = false;
done = false;
explore(1, 1);
}

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

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