2024-5-13——腐烂的橘子
2024-5-13
- 题目来源
- 我的题解
- 方法一 广度优先遍历
题目来源
力扣每日一题；题序：994
我的题解
方法一 广度优先遍历
开始找到所有的腐坏苹果，然后从这些位置开始广度优先遍历，直到队列中没有。然后判断是否还有未腐坏的苹果，若没有这将结果返回，若有则返回-1
时间复杂度：O(mn)。
空间复杂度：O(mn)。
public int orangesRotting(int[][] grid) {int res=0;int m=grid.length,n=grid[0].length;Queue<int[]> queue=new LinkedList<>();for(int i=0;i<m;i++){for(int j=0;j<n;j++){int t=grid[i][j];if(t==2){queue.offer(new int[]{i,j});}}}int[][] pos={{0,1},{0,-1},{1,0},{-1,0}};while(!queue.isEmpty()){int sz=queue.size();for(int i=0;i<sz;i++){int[] t=queue.poll();for(int[] p:pos){int x=t[0]+p[0];int y=t[1]+p[1];if(check(m,n,x,y)&&grid[x][y]==1){grid[x][y]=2;queue.offer(new int[]{x,y});}}}if(!queue.isEmpty())res++;}for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j]==1)return -1;}}return res;
}
public boolean check(int m,int n,int x,int y){return x>=0&&x<m&&y>=0&&y<n;
}
有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~