Q45 Minimum Cost to Make at Least One Valid Path in a Grid - LeetCode 1368
Fri Jun 23 2023 09:02:10 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
class Solution {
public int minCost(int[][] grid) {
/* already submitted a solution using BFS and DP
this one is simple solution using Djikstra and DP
//we will not use pair class instead use array and lambda function
*/
int m = grid.length, n = grid[0].length;
PriorityQueue<int[]> q = new PriorityQueue<>((a,b) -> a[2] - b[2]);
q.add(new int[]{0 , 0 ,0});
/* we will make a dp array which will store minimum cost for every cell , this is to avoid using visited..
as a new path can overlap an old path if it has a lesser path cost we will make this a dp array and not
visited cause then a new path will not be able to overlap a previous path as that cell will already be true
*/
int[][] costs = new int[m][n]; //dp array
for(int temp[] : costs) //filling dp array
Arrays.fill(temp , Integer.MAX_VALUE);
//djikstra algo
while(q.size() > 0){
int[] rem = q.remove();
int row = rem[0] , col = rem[1] , cost = rem[2];
if(row == m-1 && col == n-1)
return cost;
//seeing neighours
for(int i = 0 ; i < 4 ; i++){
int rowdash = row + dir[i][0];
int coldash = col + dir[i][1];
//if valid cell
if(rowdash >= 0 && coldash >= 0 && rowdash < m && coldash < n ){
/* if new cost is < previous cost we update even if we have to revsit the node -- this is
alternate to visited array */
int new_cost = cost + (i+1 == grid[row][col] ? 0 : 1);
if(new_cost < costs[rowdash][coldash]){
costs[rowdash][coldash] = new_cost;
q.add(new int[]{rowdash , coldash , new_cost});
}
}
}
}
return 69;
}
public int[][] dir = {{0,1}, {0,-1} , {1,0} , {-1,0}}; //right , left , down , up
}
content_copyCOPY
https://leetcode.com/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/?envType
Comments