// BFS.java

import java.util.Queue;
import java.util.ArrayDeque;

// a simple class for storing a position in the maze
class Point {
    public int x;
    public int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class BFS {
    public static void main(String args[]) {
        Queue<Point> queue = new ArrayDeque<Point>();

        // the maze is 18x8
        // # means wall
        // - means path
        String[] mazeString = {
            "-#################",
            "----------##-----#",
            "-########-##-##-##",
            "-########----##-##",
            "-########-#####-##",
            "-----####-#####-##",
            "#########-###---##",
            "####------#####---"};
        
        // convert to 2D array of char
        char [][] maze = new char[8][18];
        for (int i = 0; i < mazeString.length; i++) {
            for (int j = 0; j < mazeString[i].length(); j++) {
                maze[i][j] = mazeString[i].charAt(j);
            }
        }

        // start at the top left
        Point current = new Point(0, 0);

        // while we aren't at the end
        while ((current.x != 17) || (current.y != 7)) {

            // mark the spot we are at
            maze[current.y][current.x] = '*';

            // print the maze
            for (int i = 0; i < 8; i++) {
                for (int j = 0; j < 18; j++) {
                    System.out.print(maze[i][j]);
                }
                System.out.println();
            }
            System.out.println("\n");

            // mark this spot as seen
            maze[current.y][current.x] = 'X';

            // if we haven't gone left, and not out of bounds, enqueue left
            if (((current.x - 1) >= 0) && (maze[current.y][current.x - 1] == '-'))
                queue.add(new Point(current.x - 1, current.y));

            // enqueue right
            if (((current.x + 1) <= 17) && (maze[current.y][current.x + 1] == '-'))
                queue.add(new Point(current.x + 1, current.y));

            // enqueue bottom
            if (((current.y + 1) <= 7) && (maze[current.y + 1][current.x] == '-'))
                queue.add(new Point(current.x, current.y + 1));

            // enqueue top
            if (((current.y - 1) >= 0) && (maze[current.y - 1][current.x] == '-'))
                queue.add(new Point(current.x, current.y - 1));

            // if the queue is empty, we have no path!
            if (queue.isEmpty()) {
                System.out.println("No path found!");
                return;
            }

            // get the next one from the queue
            current = queue.remove();
        }

        System.out.println("We are at (" + current.x + ", " + current.y + ")");
        System.out.println("Done!");
    }
}