Not a member of GistPad yet?
Sign Up,
it unlocks many cool features!
- // 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
- 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;
- }
- }
RAW Paste Data
Copied
