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).  

Explanation / Answer

public class Maze {
     boolean[][] n; //north
     boolean[][] e; //east
     boolean[][] s; //south
    boolean[][] w; //west
    boolean end = false;
    boolean[][] wallvisited;
int n;    // dimension of maze
   
    public Maze(int n) {
        this.n = n;
  init();
        create();
    }

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

       
        n = new boolean[n+2][n+2];
        e = new boolean[n+2][n+2];
        s = new boolean[n+2][n+2];
        w = new boolean[n+2][n+2]; // initialze walls as present
        for (int x = 0; x < n+2; x++) {
            for (int y = 0; y < n+2; y++) {
                n[x][y] = true;
                e[x][y] = true;
                s[x][y] = true;
                w[x][y] = true;
            }
        }
    }
// create the maze
    private void create() {
        create(1, 1);
        for (int i = 0; i < 10; i++) {
            int x = n/2 + StdRandom.uniform(n/2);
            int y = n/2 + StdRandom.uniform(n/2);
            e[x][y] = w[x+1][y] = true; // To add some random walls
    }
    
    }
    // create the maze
    private void create(int x, int y) {
        wallvisited[x][y] = true;

        // if there is an wallnotvisited
        while (!wallvisited[x][y+1] || !wallvisited[x+1][y] || !wallvisited[x][y-1] || !wallvisited[x-1][y]) {

         
            while (true) {
   // get random neighbor
                double r = StdRandom.uniform(4);
                if (r == 0 && !wallvisited[x][y+1]) {
                    n[x][y] = false;
                    s[x][y+1] = false;
                    create(x, y + 1);
                    break;
                }
                else if (r == 1 && !wallvisited[x+1][y]) {
                    e[x][y] = false;
                    w[x+1][y] = false;
                    create(x+1, y);
                    break;
                }
                else if (r == 2 && !wallvisited[x][y-1]) {
                    s[x][y] = false;
                    n[x][y-1] = false;
                    create(x, y-1);
                    break;
                }
                else if (r == 3 && !wallvisited[x-1][y]) {
                    w[x][y] = false;
                    e[x-1][y] = false;
                    create(x-1, y);
                    break;
                }
            }
        }
    }
// solve the maze from start state
    public void solve() {
        for (int x = 1; x <= n; x++)
            for (int y = 1; y <= n; y++)
                wallvisited[x][y] = false;
        end = false;
        solve(1, 1);
    }
    // solve the maze
    private void solve(int x, int y) {
        if (x == 0 || y == 0 || x == n+1 || y == n+1) return;
        if (end || wallvisited[x][y]) return;
        wallvisited[x][y] = true;

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

        if (!n[x][y]) solve(x, y + 1);
        if (!e[x][y]) solve(x + 1, y);
        if (!s[x][y]) solve(x, y - 1);
        if (!w[x][y]) solve(x - 1, y);

        if (end) return;

    }

    public static void main(String[] args) {
        int n = Integer.parseInt(args[0]);
        Maze maze = new Maze(n);
        maze.solve();
    }

}

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

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