// User function Template for Java
class Pair
{
    int row;
    int col;
    int dist;
    Pair(int dist, int row, int col)
    {
        this.dist = dist;
        this.row = row;
        this.col = col;
    }
}

class Solution {

    int shortestPath(int[][] grid, int[] source, int[] destination) {
        // same starting and ending position
        if(source[0] == destination[0] && source[1] == destination[1])
            return 0;
            
        int n=grid.length, m=grid[0].length;
        
        // Step-1 Create a distance matrix
        int[][] distance = new int[n][m];
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                distance[i][j]=(int)1e9;
            }
        }
        distance[source[0]][source[1]] = 0;
        
        // Step-2 Store the nodes into MIN-HEAP accoriding to node's distances
        PriorityQueue<Pair> pq = new PriorityQueue<>( (x,y) -> Integer.compare(x.dist, y.dist));
        pq.add(new Pair(0, source[0], source[1]));
        
        int[] deltaRow = {-1, 0, 1, 0};
        int[] deltaCol = {0, 1, 0, -1};
        
        // Step-3 Traverse all nodes and edges
        while(!pq.isEmpty())
        {
            Pair pair = pq.poll();
            int row = pair.row;
            int col = pair.col;
            int currentDist = pair.dist;
            
            // traversing in all 4-directions
            for(int i=0; i<4; i++)
            {
                int nRow = row + deltaRow[i];
                int nCol = col + deltaCol[i];
                
                if(nRow >=0 && nRow < n && nCol >=0 && nCol < m)
                {
                    // only traverse through neighbour if it's cell value is 1
                    if(grid[nRow][nCol] == 1)
                    {
                        // if we found destination node
                        if(nRow == destination[0] && nCol == destination[1])
                            return currentDist+1;
                    
                        // checking if new distance is less than the current distance stored
                        // if yes then update it and add pair to queue
                        if(distance[nRow][nCol] > currentDist + 1)
                        {
                            distance[nRow][nCol] = currentDist + 1;
                            pq.add(new Pair(currentDist+1, nRow, nCol));
                        }
                    }
                }
            }
        }
        return -1;
    }
}