Question with regard leetcode 1091 Shortest Path in Binary Matrix

I was trying to use heuristics and priority queue to solve the leetcode 1091 Shortest Path in Binary Matrix. However, I cannot pass all the tests. Do you have any idea about the error in my code?

For example, the input is [[0,0,0],[1,1,0],[1,1,0]], the output should be 4. But, my code gets the output of 5. The heuristics I used were the direct distance between the current node to the target node.

class Solution {
    
    public int shortestPathBinaryMatrix(int[][] grid) {
        
        int side_length = grid.length;
        
        // if the s left top corner is 1 then, no path exist and return -1
        if(grid[0][0]== 1 || grid[side_length - 1][side_length - 1]== 1)
        {
            return -1;
        }
        
        if(side_length == 1)
        {
            return 1;
        }
        
        
        // 2D array for 8 directions
        int[][] directions = new int[][]{{1,0},{-1,0},{0,1},{0,-1},{-1,-1},{-1,1},{1,-1},{1,1}};
        
        
        PriorityQueue<Node> pqueue = new PriorityQueue<Node>(10,  new Comparator<Node>()
       {
            public int compare(Node i, Node j) {
                if(Double.compare(i.heuristic, j.heuristic) < 0){
                    return 100;
                }
                else
                {
                    return -100;
                }
            }
       });

        double heuristic = e_distance(0, 0, side_length - 1, side_length - 1);
        
        Node start_point = new Node(0, 0, heuristic);
        
        pqueue.add(start_point);
        
        
        boolean explored[][] = new boolean[side_length][side_length];
        
        explored[0][0] = true;
        
        int output = 1;
        
        while(!pqueue.isEmpty())
        {

            Node curr_point = pqueue.poll();
        
            
            int x = curr_point.x;
            int y = curr_point.y;
            
            explored[x][y] = true;
            
            if(x == side_length - 1 && y == side_length - 1)
            {
                    return output;
            }
            


            for(int[] successor : directions)
            {
                
                int successor_x = x + successor[0];
                int successor_y = y +  + successor[1];
                heuristic = e_distance(successor_x, successor_y, side_length - 1, side_length - 1);
                
                Node successor_point = new Node(successor_x, successor_y, heuristic);
                
                if (pqueue.contains(successor_point))
                {
                    continue;
                }
                
                
                if(successor_x >= 0 && successor_x < side_length && successor_y >= 0 
                   && successor_y < side_length && grid[successor_x][successor_y] == 0 
                   && !explored[successor_x][successor_y])
                {
                    if(successor_x == side_length - 1 && successor_y == side_length - 1)
                    {
                        return output + 1;
                    }
                    
                    pqueue.add(successor_point);
                }

                else
                {
                    continue;
                }

            }
            
            output++;

        }

        return -1;
    }

    
    public double e_distance(int x, int y, int target_x, int target_y)
    {
        return Math.sqrt(Math.abs(target_x - x) * Math.abs(target_x - x) + Math.abs(target_y - y)* Math.abs(target_y - y));
    }
    

}

public class Node{
        
        public int x;
        public int y;
        public double heuristic;
    
    
        public Node(int x, int y, double heuristic)
        {
            this.x = x;
            this.y = y;
            this.heuristic = heuristic;
        }
        
    
    }

Answer

The following is a BFS solution based on your code. It is working although it may need further debugging :

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Main   {

    public static void main(String[] args) {

        List<int[][]>grids = new ArrayList<>();
        grids.add(  new int[][] {{0,1},{1,0}} );//2
        grids.add(  new int[][]{{0,0,0},{1,1,0},{1,1,0}} ); //4
        grids.add( new int[][] {{1,0,0},{1,1,0},{1,1,0}} );//-1

        Solution s = new Solution();
        for (int[][]grid : grids) {
            System.out.println(s.shortestPathBinaryMatrix(grid));
        }
    }
}

class Solution {
    // 2D array for 8 directions
    public static int[][] DIRECTIONS = new int[][]{{1,0},{-1,0},{0,1},{0,-1},{-1,-1},{-1,1},{1,-1},{1,1}};

    public int shortestPathBinaryMatrix(int[][] grid) {

        int side_length = grid.length;

        // if the s left top corner is 1 then, no path exist and return -1
        if(grid[0][0]== 1 || grid[side_length - 1][side_length - 1]== 1)    return -1;

        if(side_length == 1)    return 1;

        Queue<Node> pqueue =  new LinkedList<>();

        Node start_point = new Node(0, 0);

        pqueue.add(start_point);

        boolean explored[][] = new boolean[side_length][side_length];//you can use grid values to mark explored
        //int output = 1; use Node.parent to mark the path

        while(!pqueue.isEmpty()){

            Node curr_point = pqueue.poll();

            int x = curr_point.x;
            int y = curr_point.y;

            explored[x][y] = true;

            if(x == side_length - 1 && y == side_length - 1)    return pathLength(curr_point);

            for(int[] successor :  DIRECTIONS)  {

                int successor_x = x + successor[0];
                int successor_y = y +  + successor[1];

                Node successor_point = new Node(successor_x, successor_y);

                if (pqueue.contains(successor_point))
                {
                    continue;
                }

                if(successor_x >= 0 && successor_x < side_length && successor_y >= 0
                        && successor_y < side_length
                        && grid[successor_y][successor_x] == 0 //NOT grid[successor_x][successor_y] == 0
                        && !explored[successor_x][successor_y])
                {
                    //if(successor_x == side_length - 1 && successor_y == side_length - 1)
                    //  return output + 1;

                    explored[successor_x][successor_y] = true; //mark as explored
                    successor_point.setParent(curr_point);     //mark as child of current node
                    pqueue.add(successor_point);
                }

                else //this else does nothing
                {
                    continue;
                }
            }
        }
        return -1;
    }

    private int pathLength(Node node) {
        if(node == null) return 0;
        int pathLength = 1;
        while (node.getParent() !=null){
            node = node.getParent();
            pathLength++;
        }
        return pathLength;
    }
}

class Node{

    public int x, y;
    public double cost;
    public Node parent = null;

    public Node(int x, int y){
        this(x, y, 0);
    }

    public Node(int x, int y, double cost)
    {
        this.x = x;  this.y = y;
        this.cost = cost;
    }

    public Node getParent() {
        return parent;
    }

    public void setParent(Node parent) {
        this.parent = parent;
    }

    //todo implement equals and hashCode 
}

A somewhat better impelementation of shortestPathBinaryMatrix :

public int shortestPathBinaryMatrix(int[][] grid) {

    int side_length = grid.length;

    // if the s left top corner is 1 then, no path exist and return -1
    if(grid[0][0]== 1 || grid[side_length - 1][side_length - 1]== 1)    return -1;

    if(side_length == 1)    return 1;

    Queue<Node> queue =  new LinkedList<>();
    queue.add(new Node(0, 0));

    while(!queue.isEmpty()){

        Node curr_point = queue.poll();
        int x = curr_point.x;   int y = curr_point.y;

        if(x == side_length - 1 && y == side_length - 1) return pathLength(curr_point);
        grid[y][x] = 1;

        for(int[] successor :  DIRECTIONS)  {

            int successor_x = x + successor[0];
            int successor_y = y +  + successor[1];

            if(successor_x >= 0 && successor_x < side_length && successor_y >= 0
                    && successor_y < side_length
                    && grid[successor_y][successor_x] == 0) {

                Node successor_point = new Node(successor_x, successor_y);

                if (queue.contains(successor_point)){
                    continue;
                }

                grid[successor_y][successor_x] = 1; //mark as explored
                successor_point.setParent(curr_point);     //mark as child of current node
                queue.add(successor_point);
            }
        }
    }
    return -1;
}

When different edjges have different cost (weighted graph) you may want to implement Dijkstra algorithm. Dijkstra algorithm is basically an enhanced BFS. This is where cost and PriorityQueue are needed.
shortestPathBinaryMatrix becomes:

    //Dijkstra's Algorithm
    public int shortestPathBinaryMatrix(int[][] grid) {

        int side_length = grid.length;

        // if the s left top corner is 1 then, no path exist and return -1
        if(grid[0][0]== 1 || grid[side_length - 1][side_length - 1]== 1)    return -1;

        if(side_length == 1)    return 1;

        PriorityQueue<Node> queue = new PriorityQueue<>(10,(i,j)-> Double.compare(i.cost, j.cost));
        queue.add(new Node(0, 0, 0));

        while(!queue.isEmpty()){

            Node curr_point = queue.poll();
            int x = curr_point.x;   int y = curr_point.y;

            if(x == side_length - 1 && y == side_length - 1) return pathLength(curr_point);

            grid[y][x] = 1;
            for(int[] successor :  DIRECTIONS)  {

                int successor_x = x + successor[0];
                int successor_y = y +  + successor[1];

                if(successor_x >= 0 && successor_x < side_length
                        && successor_y >= 0 && successor_y < side_length
                        && grid[successor_y][successor_x] == 0) {

                    double cost = curr_point.cost+1;
                    Node successor_point = new Node(successor_x, successor_y, cost);
                    if (queue.contains(successor_point)) {
                        continue;
                    }

                    grid[successor_y][successor_x] = 1; //mark as explored
                    successor_point.setParent(curr_point);     //mark as child of current node
                    queue.add(successor_point);
                }
            }
        }
        return -1;
    }

A heuristic is needed when you implement A* algorithm. A* algorithm is basically an enhanced Dijkstra algorithm.
To implement it you only need to modify the cost calculation to:
double cost = curr_point.cost+1 + heuristic ; soshortestPathBinaryMatrix becomes:

    //A* algorithm
    public int shortestPathBinaryMatrix(int[][] grid) {

        int side_length = grid.length;

        // if the s left top corner is 1 then, no path exist and return -1
        if(grid[0][0]== 1 || grid[side_length - 1][side_length - 1]== 1)    return -1;

        if(side_length == 1)    return 1;

        PriorityQueue<Node> queue = new PriorityQueue<>(10,(i,j)-> Double.compare(i.cost, j.cost));
        queue.add(new Node(0, 0, 0));

        while(!queue.isEmpty()){

            Node curr_point = queue.poll();
            int x = curr_point.x;   int y = curr_point.y;

            if(x == side_length - 1 && y == side_length - 1) return pathLength(curr_point);

            grid[y][x] = 1;
            for(int[] successor :  DIRECTIONS)  {

                int successor_x = x + successor[0];
                int successor_y = y +  + successor[1];

                if(successor_x >= 0 && successor_x < side_length
                        && successor_y >= 0 && successor_y < side_length
                        && grid[successor_y][successor_x] == 0) {

                    double cost = curr_point.cost+1 + distance(successor_x, successor_y, x, y);
                    Node successor_point = new Node(successor_x, successor_y, cost);
                    if (queue.contains(successor_point)) {
                        continue;
                    }

                    grid[successor_y][successor_x] = 1; //mark as explored
                    successor_point.setParent(curr_point);     //mark as child of current node
                    queue.add(successor_point);
                }
            }
        }
        return -1;
    }

and distance is defined as:

    public double distance(int x, int y, int targetX, int targetY)   {
       return Math.sqrt(Math.pow(targetX - x,2) + Math.pow(targetY - y,2));
    }