//BFS : dijkstra'sclassSolution{publicintminimumObstacles(int[][]grid){intminObstacleRemoved=Integer.MAX_VALUE;Queue<Cell>q=newPriorityQueue<>((a,b)->Integer.compare(a.c,b.c));intvisited[][]=newint[grid.length][grid[0].length];q.add(newCell(0,0,0));while(!q.isEmpty()){Cellcell=q.remove();intI=cell.i;intJ=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;}intdirs[][]={{0,-1},{0,1},{-1,0},{1,0}};intobstacleRemovedSoFar=cell.c;for(intdir[]:dirs){inti=I+dir[0];intj=J+dir[1];if(i>=0&&j>=0&&i<grid.length&&j<grid[0].length&&visited[i][j]==0){intc=obstacleRemovedSoFar;//if it is an obstacle then 1 more obstacle you will have to removeif(grid[i][j]==1)c+=1;q.add(newCell(i,j,c));}}}returnminObstacleRemoved;}}classCell{inti;intj;intc;publicCell(inti,intj,intc){this.i=i;this.j=j;this.c=c;}}