int[] start = new int[2] ;
int[] exit = new int[2];
char[][] maze={ {'H','H','H','H','H','H','H','H','H','H','H','H','H','H','H','H'},
                {'H','E','.','.','.','H','.','H','.','.','.','.','.','.','H','H'},
                {'H','.','H','H','H','.','.','.','.','H','.','H','H','.','.','H'},
                {'H','.','H','H','H','.','H','H','.','H','.','H','H','.','H','H'},
                {'H','.','.','.','.','.','.','H','.','H','.','.','.','.','H','H'},
                {'H','.','H','H','.','.','H','H','.','H','.','H','H','.','.','H'},
                {'H','H','.','H','H','.','.','.','.','H','.','.','.','.','H','H'},
                {'H','.','.','H','H','.','H','H','H','.','.','H','H','.','H','H'},
                {'H','H','.','.','.','.','.','S','.','H','.','.','.','.','H','H'},
                {'H','H','H','.','H','H','.','H','.','H','.','H','H','.','.','H'},
                {'H','.','H','.','.','.','.','H','.','H','.','H','.','H','.','H'},
                {'H','H','.','.','H','H','H','H','.','.','.','H','.','H','.','H'},
                {'H','.','H','H','H','.','H','H','H','.','H','.','.','.','.','H'},
                {'H','.','.','.','.','.','.','.','.','.','H','.','H','.','H','H'},
                {'H','H','H','.','H','.','H','.','H','.','H','.','H','.','H','H'},
                {'H','H','H','H','H','H','H','H','H','H','H','H','H','H','H','H'},};
NodeInfo[][] graph = new NodeInfo[maze.length][maze.length];
boolean[][] traversed= new boolean[maze.length][maze.length] ;
for(int r=0;r<maze.length;r++)
{
    for(int c=0;c<maze[r].length;c++)
    {
        if(maze[r][c]=='E')
        {
            start[0]=r;
            start[1]=c;
        }
        if(maze[r][c]=='S')
        {
            exit[0]=r;
            exit[1]=c;
        }
        if(maze[r][c]!='H')
        {
            traversed[r][c]=true;
            int[] tempo = {r,c} ;
            graph[r][c]=new NodeInfo(tempo);
        }
        else
        {
            traversed[r][c]=false;
            int[] tempo = {r,c} ;
            graph[r][c]=new NodeInfo() ;
        }
    }
}
boolean canSolve = false;
int minDist =Integer.MAX_VALUE ;
NodeInfo starter = new NodeInfo(start) ;
starter.setDist(0);
PriorityQueue<NodeInfo> q = new PriorityQueue<NodeInfo>(10, new Comparator<NodeInfo>()
{
    public int compare( NodeInfo node1, NodeInfo node2)
    {
        if(node1.getDist()<node2.getDist()) return -1;
        if(node1.getDist()>node2.getDist()) return 1;
        return 0;
    }
}) ;
starter.setPred(null) ;
q.add(starter) ;
while(!q.isEmpty())
{
    traversed[q.peek().getRay()[0]][q.peek().getRay()[1]]=false;
    if(maze[q.peek().getRay()[0]][q.peek().getRay()[1]]=='S')
    {
        canSolve = true;
        int r,c;
        r=q.peek().getRay()[0];
        c=q.peek().getRay()[1];

        if(minDist>graph[r][c].getDist())
            minDist=graph[r][c].getDist();
    }
    if(traversed[q.peek().getRay()[0]][q.peek().getRay()[1]+1]==true)
    {
        int r,c;
        r=q.peek().getRay()[0];
        c=q.peek().getRay()[1]+1;
        graph[r][c].setDist(q.peek().getDist()+graph[r][c].getEdge());
        graph[r][c].setPred(graph[q.peek().getRay()[0]][q.peek().getRay()[1]].getRay());
        q.add(graph[r][c]);

    }
    if(traversed[q.peek().getRay()[0]][q.peek().getRay()[1]-1]==true)
    {
        int r,c;
        r=q.peek().getRay()[0];
        c=q.peek().getRay()[1]-1;
        graph[r][c].setDist(q.peek().getDist()+graph[r][c].getEdge());
        graph[r][c].setPred(graph[q.peek().getRay()[0]][q.peek().getRay()[1]].getRay());
        q.add(graph[r][c]);

    }
    if(traversed[q.peek().getRay()[0]+1][q.peek().getRay()[1]]==true)
    {
        int r,c;
        r=q.peek().getRay()[0]+1;
        c=q.peek().getRay()[1];
        graph[r][c].setDist(q.peek().getDist()+graph[r][c].getEdge());
        graph[r][c].setPred(graph[q.peek().getRay()[0]][q.peek().getRay()[1]].getRay());
        q.add(graph[r][c]);

    }
    if(traversed[q.peek().getRay()[0]-1][q.peek().getRay()[1]]==true)
    {
        int r,c;
        r=q.peek().getRay()[0]-1;
        c=q.peek().getRay()[1];
        graph[r][c].setDist(q.peek().getDist()+graph[r][c].getEdge());
        graph[r][c].setPred(graph[q.peek().getRay()[0]][q.peek().getRay()[1]].getRay());
        q.add(graph[r][c]);

    }
    q.poll() ;
}

if(minDist!=Integer.MAX_VALUE)
{
    LinkedList<int[]> steps = new LinkedList();
    System.out.println(" Number Of Steps Taken : "+minDist + "n Maze is solvable : " + canSolve) ;
    int r,c;
    r=exit[0];
    c=exit[1];
    steps.add(exit);
    boolean griph=true;
    while(griph)
    {

        if(griph)
        {
            int rows=r;
            int cols=c;
            if(graph[r][c].getPred()==null)
            {
                griph=false;
            }
            if(griph==true)
            {
            if(maze[r][c]=='.')
            {
            maze[r][c]='x';
            }
            steps.addLast(graph[r][c].getPred());
            r=graph[rows][cols].getPred()[0];
            c=graph[rows][cols].getPred()[1];
            }
        }

    }
    while(!steps.isEmpty())
    {
        System.out.println(Arrays.toString(steps.pollLast())+" ");
    }
}
else
    System.out.println("Maze is Solvable : "+canSolve) ;

for(int r= 0; r<maze.length;r++)
{
    for(int c= 0; c<maze.length;c++)
    {
        System.out.print(maze[r][c]+" ");
        if(c+1==maze.length)
            System.out.println();
    }
}