Implementation Finding maze program using Stack(DFS, Backtracking)

It's a one of the assignments of the Data Structure.

There are several condition of assignment.

1. Stack must be implemented using an Array.

2. Finding maze program must be implimented using stack that I implement

Actually I've implemented finding maze and similar things on baekjoon site that is famous online judge site of korean.

So, these assignments are very easy to me.

To implement Finding maze, you have know algorithm DFS and Backtracking.

If you want to check only that this maze is possible, you don't have to know about backtracking.

but, If you want to know the route, you have to know backtracking.

It is first time to implement DFS using stack not recursion.

 

Here are stack and Maze code.

Java is used in the lecture.

public class ArrayStack<T> implements Stack<T> {
    public static final int MaxSize = 100;
    private final T[] elements;
    private int top = -1;
    private int capacity = 0;

    @SuppressWarnings("unchecked")
    public ArrayStack() {
        elements = (T[]) new Object[MaxSize];
        this.capacity = MaxSize;
    }

    @SuppressWarnings("unchecked")
    public ArrayStack(int capacity) {
        elements = (T[]) new Object[capacity];
        this.capacity = capacity;
    }

    @Override
    public void push(T obj) {
        if (isFull())
            throw new FullStackException("Stack Overflow");

        elements[++top] = obj;
    }

    @Override
    public T pop() throws EmptyStackException {
        if (isEmpty()) {
            throw new EmptyStackException("Stack Underflow");
        }
        T tmp = elements[top];
        elements[top--] = null;
        return tmp;
    }

    @Override
    public T top() {
        if (isEmpty()) {
            throw new EmptyStackException("Stack Underflow");
        }
        return elements[top];
    }

    @Override
    public boolean isEmpty() {
        return top == -1;
    }

    @Override
    public boolean isFull() {
        return top == capacity - 1;
    }
}

 

If you use pop method when the stack is empty, of course error is occurred.(given)

import java.io.Serial;

public class EmptyStackException extends RuntimeException {
    @Serial
    private static final long serialVersionUID = 1L;

    public EmptyStackException() {
        super();
    }

    public EmptyStackException(String e) {
        super(e);
    }
}

 

If you use push method when stack is full, error is occurred too.(given)

import java.io.Serial;

public class FullStackException extends RuntimeException {
    @Serial
    private static final long serialVersionUID = 1L;

    public FullStackException() {
        super();
    }

    public FullStackException(String e) {
        super(e);
    }
}

 

 

 

And Here are the maze code. I record all path from start to exit on the stack.

first, it is location class to save coordinate in the stack.(given)

public class Location {
    public int row;
    public int col;

    /**
     * Constructs a location with given row and column coordinates.
     * @param row  	row index
     * @param col	column index
     */
    public Location(int row, int col) {
        this.row = row;
        this.col = col;
    }

    public String toString() {
        return "[" + row + "," + col + "]";
    }
}

 

 

Next code is maze. The method that is used DFS and Backtracking algorithm is moveTo.

1 is the wall you can't go, and 0 is the route.

This code work regardless of starting point and exit point.

import java.util.Arrays;

public class Maze {
    private final int numRows; // number of rows
    private final int numCols; // number of columns

    private int[][] maze; // maze itself
    private boolean[][] visited; // true if cell was visited before

    private final Location entry; // Entry Location
    private final Location exit;  // Exit Location

    private final ArrayStack<Location> stack = new ArrayStack<>(100);

    private int[] dy = {1,-1,0,0};
    private int[] dx = {0,0,-1,1};

    /**
     * Initialize this maze with a given maze and entry/exit locations.
     * @param maze	2D array representing a maze
     * @param entry	entry location
     * @param exit	exit location
     */
    public Maze(int[][] maze, Location entry, Location exit) {
        this.maze = maze;
        numRows = maze.length;
        numCols = maze[0].length;

        visited = new boolean[numRows][numRows];
        for (int i = 0; i < numRows; i++) {
            Arrays.fill(visited[i], false);
        }
        this.entry = entry;
        this.exit = exit;
    }

    // For testing purpose, you don't have to care this.
    public void printMaze() {
        System.out.println("Maze[" + numRows + "][" + numCols + "]");
        System.out.println("Entry index = (" + entry.row + ", " + entry.col + ")");
        System.out.println("Exit index = (" + exit.row + ", " + exit.col + ")" + "\n");

        for (int i = 0; i < numRows; i++) {
            System.out.println(Arrays.toString(maze[i]));
        }
        System.out.println();
    }

    public boolean findPath() {
        return moveTo(entry.row, entry.col);
    }

	/* Core method */
    private boolean moveTo(int row, int col) {
        visited[row][col] = true;
        stack.push(new Location(row, col));
        while(!stack.isEmpty()){
            int x = stack.top().row;
            int y = stack.top().col;
            for(int i = 0; i < 4; i++){
                int tmp_x = x + dx[i];
                int tmp_y = y + dy[i];
                if (0 <= tmp_x && tmp_x < numRows && 0 <= tmp_y && tmp_y < numCols){
                    if(maze[tmp_x][tmp_y] == 0 && !visited[tmp_x][tmp_y]){
                        check = true;
                        visited[tmp_x][tmp_y] = true;
                        stack.push(new Location(tmp_x,tmp_y));
                        if(stack.top().row == exit.row && stack.top().col == exit.col){
                            return true;
                        }
                        break;
                    }
                }
            }
            if(check) continue;
            stack.pop();
        }

        return false;
    }


    public String showPath() {
        StringBuilder builder = new StringBuilder();
        while (!stack.isEmpty()) {
            builder.append(stack.pop() + " <-- ");
        }
        builder.append("Start");
        System.out.println(builder);
        return builder.toString();
    }


}

 

As you can see, I use private int array(dx, dy) to search direction. (order is east -> west -> south -> north.)

For example, I search 0 east, west, south and north at starting point. And if east point is 0, I push that on the stack.

If, there is not another route(0), I pop the top of stack(most recently point) and continue for loop(search the west).

The above process is called backtracking, and if you continue to repeat it, only the path to the exit remains in the stack.