package com.company;
class Coordinates{
    public int x,y;                 //for storing coordinates as object
    Coordinates(int x,int y){
        this.x=x;
        this.y=y;
    }
}
public class BFS {                      //BFS main class
    static Coordinates[] queue=new Coordinates[1000];         //queue of coordinates
    private static int front=-1;
    private static int rear=-1;


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

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

    static void bfs(char[][] maze,Coordinates start,boolean[][] visited){
        int curx;
        int cury;
        for(int i=0;i<4;i++){
            curx=start.x;
            cury=start.y;
            curx+=dir[i][0];
            cury+=dir[i][1];
            if(curx<0 || cury<0 || curx> maze.length-1 || cury>maze.length-1){
                continue;                                                           //for square...  out of maze check
            }
            else if(maze[curx][cury]=='$'){
                System.out.println("Path found");
                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;
            }
        }
        dequeue();
        if(front==-1){
            System.out.println("path not found");
            System.exit(0);
        }
        else
            bfs(maze,queue[front],visited);
    }
    public static void main(String[] args) {
        char[][] maze = {{'*','#','#'},
                         {'_','_','#'},
                          {'_','#','$'},
        };
        Coordinates start=new Coordinates(0,0);
        boolean[][] visited=new boolean[maze.length][maze.length];
        for(int i=0;i< maze.length;i++){
            for(int j=0;j<maze.length;j++)  {
                visited[i][j]=false;
            }
        }
        visited[0][0]=true;
        enqueue(start);
        bfs(maze,start,visited);
    }
}