//my solutionclassSolution{publicintorangesRotting(int[][]grid){//n2 to find the first rotten tomatoQueue<Indices>q=newLinkedList<>();for(inti=0;i<grid.length;i++){for(intj=0;j<grid[0].length;j++){if(grid[i][j]!=2)continue;q.add(newIndices(i,j));}}//do breadth first search to set all the tomatos rotteninttimer=0;while(!q.isEmpty()){intsize=q.size();booleannewRotting=false;while(size-->0){Indicesin=q.remove();//leftif(in.j-1>=0&&grid[in.i][in.j-1]==1){grid[in.i][in.j-1]=2;newRotting=true;q.add(newIndices(in.i,in.j-1));}//rightif(in.j+1<grid[0].length&&grid[in.i][in.j+1]==1){grid[in.i][in.j+1]=2;newRotting=true;q.add(newIndices(in.i,in.j+1));}//upif(in.i-1>=0&&grid[in.i-1][in.j]==1){grid[in.i-1][in.j]=2;newRotting=true;q.add(newIndices(in.i-1,in.j));}//downif(in.i+1<grid.length&&grid[in.i+1][in.j]==1){grid[in.i+1][in.j]=2;newRotting=true;q.add(newIndices(in.i+1,in.j));}}if(newRotting)timer++;}//n^2 to check if there are any tomatos left freash if yes return -1 else return minutes elapsed.for(inti=0;i<grid.length;i++){for(intj=0;j<grid[0].length;j++){if(grid[i][j]==1)return-1;}}for(inti=0;i<grid.length;i++){for(intj=0;j<grid[0].length;j++){System.out.print(grid[i][j]);}System.out.println();}returntimer;}}classIndices{inti;intj;publicIndices(inti,intj){this.i=i;this.j=j;}}
// second solution from one of the submission that I saw//great solutionclassSolution{publicintorangesRotting(int[][]grid){intm=grid.length,n=grid[0].length,i,j,k=0,fresh=0,fr;for(i=0;i<m;i++)for(j=0;j<n;j++)if(grid[i][j]==1)fresh++;while(fresh>0){fr=fresh;for(i=0;i<m;i++){for(j=0;j<n;j++){if(grid[i][j]==2){if(i+1<m&&grid[i+1][j]==1){grid[i+1][j]=3;fresh--;}if(i-1>=0&&grid[i-1][j]==1){grid[i-1][j]=3;fresh--;}if(j-1>=0&&grid[i][j-1]==1){grid[i][j-1]=3;fresh--;}if(j+1<n&&grid[i][j+1]==1){grid[i][j+1]=3;fresh--;}}}}for(i=0;i<m;i++)for(j=0;j<n;j++)if(grid[i][j]==3)grid[i][j]=2;if(fr==fresh)return-1;k++;}returnk;}}
Top comments (0)
Subscribe
For further actions, you may consider blocking this person and/or reporting abuse
Top comments (0)