DEV Community

Prashant Mishra
Prashant Mishra

Posted on

Minimum obstacle removal to reach corner

TC:O(n*mlog(n*m))
SC :O(n*m)

Problem

//BFS : dijkstra's
class Solution {
    public int minimumObstacles(int[][] grid) {
        int minObstacleRemoved = Integer.MAX_VALUE;
        Queue<Cell> q = new PriorityQueue<>((a,b)-> Integer.compare(a.c,b.c));
        int visited[][]  = new int[grid.length][grid[0].length];
        q.add(new Cell(0,0,0));
        while(!q.isEmpty()){
            Cell cell = q.remove();
            int I  = cell.i;
            int J = cell.j;
            if(visited[I][J] ==1) continue;
            visited[I][J] = 1;
            if(I == grid.length-1 && J == grid[0].length-1) {
                minObstacleRemoved = cell.c;
                break;
            }
            int dirs[][] = {{0,-1},{0,1},{-1,0},{1,0}};
            int obstacleRemovedSoFar = cell.c;
            for(int dir[]: dirs){
                int i = I + dir[0];
                int j = J + dir[1];
                if(i>=0 && j>=0 && i<grid.length && j< grid[0].length && visited[i][j]==0){
                    int c = obstacleRemovedSoFar;
                    //if it is an obstacle then 1 more obstacle you will have to remove
                    if(grid[i][j]==1) c+=1;
                    q.add(new Cell(i,j,c));
                }
            }
        }
        return minObstacleRemoved;
    }

}
class Cell{
    int i;
    int j;
    int c;
    public Cell(int i, int j, int c){
        this.i = i;
        this.j = j;
        this.c = c;
    }
}
Enter fullscreen mode Exit fullscreen mode

Do your career a big favor. Join DEV. (The website you're on right now)

It takes one minute, it's free, and is worth it for your career.

Get started

Community matters

Top comments (0)

👋 Kindness is contagious

Explore a sea of insights with this enlightening post, highly esteemed within the nurturing DEV Community. Coders of all stripes are invited to participate and contribute to our shared knowledge.

Expressing gratitude with a simple "thank you" can make a big impact. Leave your thanks in the comments!

On DEV, exchanging ideas smooths our way and strengthens our community bonds. Found this useful? A quick note of thanks to the author can mean a lot.

Okay