Maze.java

import java.awt.*;
import java.util.ArrayList;
import java.util.Stack;

public class Maze {

    private Point startingPoint;
    private Point destinationPoint;
    private ArrayList<Point> walls;
    private ArrayList<Point> path;

    private int maxX;
    private int maxY;
    private Node solution;

    public Maze(String maze) {
        ArrayList<Point> walls = new ArrayList<>();
        ArrayList<Point> path = new ArrayList<>();
        int x = 0;
        int y = 0;
        for (int i = 0; i < maze.length(); i++)  {
            if (maze.charAt(i) == '\n') {
                y++;
                x = 0;
                continue;
            }
            if (x > maxX) maxX = x;
            if (y > maxY) maxY = y;
            if (maze.charAt(i) == '#') {
                walls.add(new Point(x, y));
            } else if (maze.charAt(i) == ' ') {
                path.add(new Point(x, y));
            } else if (maze.charAt(i) == 'A') {
                startingPoint = new Point(x, y);
            } else if (maze.charAt(i) == 'B') {
                destinationPoint = new Point(x, y);
                path.add(destinationPoint);
            }
            x++;
        }
        this.walls = walls;
        this.path = path;
    }

    private ArrayList<Node> getNeighbors(Node node) {
        ArrayList<Node> result = new ArrayList<>();
        Point top = new Point(node.getState().x, node.getState().y - 1);
        Point bottom = new Point(node.getState().x, node.getState().y + 1);
        Point left = new Point(node.getState().x - 1, node.getState().y);
        Point right = new Point(node.getState().x + 1, node.getState().y);
        if (path.contains(top)) result.add(new Node(top, node));
        if (path.contains(bottom)) result.add(new Node(bottom, node));
        if (path.contains(right)) result.add(new Node(right, node));
        if (path.contains(left)) result.add(new Node(left, node));
        return result;
    }

    public Node solve() {
        ArrayList<Point> visited = new ArrayList<>();

        // Create frontier that has only the initial state.
        Stack<Node> frontier = new Stack<>(); // OR QUEUE.
        frontier.add(new Node(startingPoint, null));

        // Repeat the following:
        //      1. If frontier is empty, return no solution.
        //      2. Remove an element, if it's out destination, we're done.
        //      3. Add neighbours to the frontier
        while (true) {
            if (frontier.isEmpty()) return null;
            Node temp = frontier.pop();
            if (temp.getState().equals(destinationPoint)) return solution = temp;

            for (Node node : getNeighbors(temp)) {
               if (!visited.contains(node.getState())) {
                    visited.add(node.getState());
                    frontier.add(node);
                }
            }

        }

    }

    public void print() {
        if (solution == null) return;
        Node tempSolution = solution;
        ArrayList<Point> correctPath = new ArrayList<>();
        while (tempSolution.getParent() != null) {
            correctPath.add(tempSolution.getState());
            tempSolution = tempSolution.getParent();
        }

        for (int i = 0; i <= maxY; i++) {
            for (int j = 0; j <= maxX; j++) {
                Point temp = new Point(j, i);
                if (startingPoint.equals(temp)) {
                    System.out.printf("A");
                } else if (destinationPoint.equals(temp)) {
                    System.out.printf("B");
                } else if (walls.contains(temp)) {
                    System.out.printf("%c", '#');
                } else if (correctPath.contains(temp)) {
                    System.out.printf("+");
                } else {
                    System.out.printf(" ");
                }
            }
            System.out.println();
        }
    }
}