class BFS {
    // queue of coordinates.
    static Coordinates[] queue = new Coordinates[1000];
    private static int front = -1;
    private static int rear = -1;

    static void enqueue(Coordinates coord) {
        if (front == -1 && rear == -1) {
            front = 0;
            rear = 0;
        } else {
            rear++;
        }
        queue[rear] = coord;
    }

    static void dequeue() {
        if (front == rear) {
            front = -1;
            rear = -1;
        } else {
            front++;
        }
    }

    // traversing directions.
    private static final int[][] dir = new int[][]{
        {+0, +1}, // right.
        {+1, +0}, // down.
        {+0, -1}, // left.
        {-1, +0}, // up.
    };

    static void bfs(char[][] maze, Coordinates start, boolean[][] visited,Coordinates [][] path) {
        for (int i = 0; i < 4; i++) {
            int curx = start.x + dir[i][0];
            int cury = start.y + dir[i][1];

            // Out of bounds check.
            if (curx < 0 || cury < 0
                || curx > maze.length - 1 || cury > maze[0].length - 1)
                continue;

            // Marker cell.
            if (maze[curx][cury] == '#')
                System.out.print("!");

            // Print the maze on every iteration.
            for(int j = 0; j < maze.length; j++)
                for(int k = 0; k < maze[j].length; k++) {
                    if (maze[j][k] == '^' || maze[j][k] == '$')
                        System.out.print(maze[j][k]);
                    else {
                        if (j == curx && k == cury)
                            System.out.print("@");
                        else {
                            if (visited[j][k])
                                System.out.print("-");
                            else
                                System.out.print(maze[j][k]);
                        }
                    }
                }
            System.out.println();
            if (maze[curx][cury] == '$') {
                path[curx][cury] = new Coordinates(start.x,start.y);

                boolean[][] printpath = new boolean[maze.length][maze[0].length];

                for (int q = 0; q < maze.length; q++) {
                    for (int j = 0; j < maze[q].length; j++) {
                        printpath[q][j] = false;
                    }
                }

                printpath[0][0]=true;                   //start as true
                while(curx != 0 || cury != 0){
                    printpath[curx][cury] = true;
                    int temp = curx;
                    curx = path[curx][cury].x;
                    cury = path[temp][cury].y;

                    //path stores parent of current coordinate
                }

                // Marker cell.
                System.out.print("|");
                for(int j = 0; j < maze.length; j++)
                    for(int k = 0; k < maze[j].length; k++) {
                        if (maze[j][k] == '^' || maze[j][k] == '$')
                            System.out.print(maze[j][k]);
                        else {
                            if (j == curx && k == cury)
                                System.out.print("@");
                            else {
                                if(printpath[j][k])
                                    System.out.print("~");
                                else if (visited[j][k])
                                    System.out.print("-");
                                else
                                    System.out.print(maze[j][k]);
                            }
                        }
                    }
                System.out.println();
                System.exit(0);
            } else if (visited[curx][cury] || maze[curx][cury] == '#') {
                continue;
            } else if(maze[curx][cury]=='.') {
                enqueue(new Coordinates(curx, cury));
                visited[curx][cury] = true;
                path[curx][cury]=new Coordinates(start.x,start.y);
            }
        }
        dequeue();
        if (front == -1) {
            System.out.println("path not found");
            System.exit(0);
        } else {
            bfs(maze, queue[front], visited, path);
        }
    }

    public static void main(String[] args) {
        char[][] maze = {
            { '^', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', },
            { '.', '.', '.', '.', '#', '.', '.', '.', '.', '.', '.', '.', '.', },
            { '.', '.', '.', '.', '#', '.', '.', '.', '.', '.', '.', '.', '.', },
            { '.', '.', '.', '.', '#', '#', '#', '.', '.', '.', '.', '.', '.', },
            { '.', '.', '#', '#', '.', '#', '.', '.', '.', '.', '.', '.', '.', },
            { '.', '.', '.', '.', '.', '#', '.', '.', '.', '.', '.', '.', '.', },
            { '.', '.', '.', '.', '.', '#', '.', '#', '#', '.', '#', '#', '#', },
            { '.', '.', '.', '.', '.', '#', '.', '#', '.', '.', '.', '.', '.', },
            { '.', '.', '.', '.', '.', '#', '.', '#', '.', '.', '.', '$', '.', },
            { '.', '.', '.', '.', '.', '#', '.', '#', '.', '.', '.', '.', '.', },
            { '.', '.', '.', '.', '.', '.', '.', '#', '.', '.', '.', '.', '.', },
            { '.', '.', '.', '.', '.', '#', '.', '.', '.', '.', '.', '.', '.', },
            // {'^', '#', '.'},
            // {'.', '.', '#'},
            // {'.', '.', '$'},
        };

        Coordinates start = new Coordinates(0,0);
        boolean[][] visited = new boolean[maze.length][maze[0].length];
        Coordinates[][] path = new Coordinates[maze.length][maze[0].length];

        System.out.println(String.format("rows:%d cols:%d", maze.length, maze[0].length));

        for (int i = 0; i < maze.length; i++)
            for (int j = 0; j < maze[i].length; j++) {
                visited[i][j] = false;
                path[i][j] = new Coordinates(0, 0);
                System.out.print(maze[i][j]);
            }
        System.out.println();

        visited[0][0] = true;
        enqueue(start);
        bfs(maze, start, visited,path);
    }
}

class Coordinates {
    // for storing coordinates as object.
    public int x, y;

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