Suppose we need to determine whether or not a particular maz

Suppose we need to determine whether or not a particular maze can be solved. We will think of the maze as composed of tall thick green hedges surrounding numerous paths. There will be a single entrance to the maze and a place where we want to get: the goal. On the computer, a maze will be a two-dimensional array of characters such: HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH H H H H H H H HHHHHHH HHHHH H H HHHHHHHHHH H HHHHH HHH HHHH H H H H H H H H H H H H H H H H H HHHHH HHH H H HHH HHHHH H H H HHHHH HHH HHH E H H H H GH H H H H H H HHH HHHHHHH HHHHHHH H H H H H HHHHHHH H HHH HH HH H H H H H H H H H H H H H HHH HHHHH HHHHHHHHH H HH H H H HHHHH HH HHH H H H H H H H H H H H H H HHH H H HHH H H HHH HHH HHH HHH H HHHHHHH H H H H H H H H H H H H H H H H HH H H H H H H H H H H H H H H HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH Where each \'H\' represents the hedge, the \'E\' represent the entrance to the maze, the \'G\' represents the goal position and the blanks represent the paths between hedges. We will assume that the maze is stored in file called maze. Write a Java programe to: 1. Read in the maze. 2. Mark all location tried with a dot \".\" and print the new maze to a file call maze.out. 3. Print message to say whether there is a path to the goal or not.

Solution

public class Maze {
private int n; // size of maze
private boolean[][] nrth;   
private boolean[][] est;
private boolean[][] sth;
private boolean[][] wst;
private boolean[][] vstd;
private boolean dne = false;

public Maze(int n) {
this.n = n;
Stddrws.setXscale(0, n+2);
Stddrws.setYscale(0, n+2);
init();
gnrt();
}

private void init() {
  
vstd = new boolean[n+2][n+2];
for (int x = 0; x < n+2; x++) {
vstd[x][0] = true;
vstd[x][n+1] = true;
}
for (int y = 0; y < n+2; y++) {
vstd[0][y] = true;
vstd[n+1][y] = true;
}

nrth = new boolean[n+2][n+2];
est = new boolean[n+2][n+2];
sth = new boolean[n+2][n+2];
wst = new boolean[n+2][n+2];
for (int x = 0; x < n+2; x++) {
for (int y = 0; y < n+2; y++) {
nrth[x][y] = true;
est[x][y] = true;
sth[x][y] = true;
wst[x][y] = true;
}
}
}

private void gnrt(int x, int y) {
vstd[x][y] = true;

  
while (!vstd[x][y+1] || !vstd[x+1][y] || !vstd[x][y-1] || !vstd[x-1][y]) {

while (true) {
double r = StdRandom.uniform(4);
if (r == 0 && !vstd[x][y+1]) {
nrth[x][y] = false;
sth[x][y+1] = false;
gnrt(x, y + 1);
break;
}
else if (r == 1 && !vstd[x+1][y]) {
est[x][y] = false;
wst[x+1][y] = false;
gnrt(x+1, y);
break;
}
else if (r == 2 && !vstd[x][y-1]) {
sth[x][y] = false;
nrth[x][y-1] = false;
gnrt(x, y-1);
break;
}
else if (r == 3 && !vstd[x-1][y]) {
wst[x][y] = false;
est[x-1][y] = false;
gnrt(x-1, y);
break;
}
}
}
}

  
private void gnrt() {
gnrt(1, 1);

}

  
private void slve(int x, int y) {
if (x == 0 || y == 0 || x == n+1 || y == n+1) return;
if (dne || vstd[x][y]) return;
vstd[x][y] = true;

Stddrws.setPenColor(Stddrws.BLUE);
Stddrws.filledCircle(x + 0.5, y + 0.5, 0.25);
Stddrws.show();
Stddrws.pause(30);

if (x == n/2 && y == n/2) dne = true;

if (!nrth[x][y]) slve(x, y + 1);
if (!est[x][y]) slve(x + 1, y);
if (!sth[x][y]) slve(x, y - 1);
if (!wst[x][y]) slve(x - 1, y);

if (dne) return;

Stddrws.setPenColor(Stddrws.GRAY);
Stddrws.filledCircle(x + 0.5, y + 0.5, 0.25);
Stddrws.show();
Stddrws.pause(30);
}

  
public void slve() {
for (int x = 1; x <= n; x++)
for (int y = 1; y <= n; y++)
vstd[x][y] = false;
dne = false;
slve(1, 1);
}

public void drws() {
Stddrws.setPenColor(Stddrws.RED);
Stddrws.filledCircle(n/2.0 + 0.5, n/2.0 + 0.5, 0.375);
Stddrws.filledCircle(1.5, 1.5, 0.375);

Stddrws.setPenColor(Stddrws.BLACK);
for (int x = 1; x <= n; x++) {
for (int y = 1; y <= n; y++) {
if (sth[x][y]) Stddrws.line(x, y, x+1, y);
if (nrth[x][y]) Stddrws.line(x, y+1, x+1, y+1);
if (wst[x][y]) Stddrws.line(x, y, x, y+1);
if (est[x][y]) Stddrws.line(x+1, y, x+1, y+1);
}
}
Stddrws.show();
Stddrws.pause(1000);
}

public static void main(String[] ahha) {
int n = Integer.parseInt(ahha[0]);
Maze maze = new Maze(n);
Stddrws.enableDoubleBuffering();
maze.drws();
maze.slve();
}

}