題目：

在給定的網(wǎng)格中，每個單元格可以有以下三個值之一：

• 值?0?代表空單元格；
• 值?1?代表新鮮橘子；
• 值?2?代表腐爛的橘子。

每分鐘，任何與腐爛的橘子（在 4 個正方向上）相鄰的新鮮橘子都會腐爛。

返回直到單元格中沒有新鮮橘子為止所必須經(jīng)過的最小分鐘數(shù)。如果不可能，返回?-1。

?

分析：

最近在看廣度優(yōu)先搜素的題目，這個是比較簡單基礎(chǔ)的題了。

腐爛的橘子會把靠近他的新鮮的橘子腐蝕，那么就是只要從所有壞的橘子的地方一層一層往外遍歷就可以了。

代碼：

1 //5ms 97% 2 class Solution { 3 public int orangesRotting(int[][] grid) { 4 Queue<int[]> q=new LinkedList<>(); 5 int h=grid.length,w=grid[0].length,time=0; 6 for(int n=0;n<h;++n) 7 for(int m=0;m<w;++m) 8 if(grid[n][m]==2) { 9 int[] po= {0,n,m}; 10 q.add(po); 11 } 12 while(!q.isEmpty()) { 13 int[] g=q.poll(); 14 time=time>g[0]?time:g[0]; 15 if(g[1]+1<h&&grid[g[1]+1][g[2]]==1) { 16 grid[g[1]+1][g[2]]=2; 17 int[] po= {g[0]+1,g[1]+1,g[2]}; 18 q.add(po); 19 } 20 if(g[1]-1>=0&&grid[g[1]-1][g[2]]==1) { 21 grid[g[1]-1][g[2]]=2; 22 int[] po= {g[0]+1,g[1]-1,g[2]}; 23 q.add(po); 24 } 25 if(g[2]-1>=0&&grid[g[1]][g[2]-1]==1) { 26 grid[g[1]][g[2]-1]=2; 27 int[] po= {g[0]+1,g[1],g[2]-1}; 28 q.add(po); 29 } 30 if(g[2]+1<w&&grid[g[1]][g[2]+1]==1) { 31 grid[g[1]][g[2]+1]=2; 32 int[] po= {g[0]+1,g[1],g[2]+1}; 33 q.add(po); 34 } 35 } 36 for(int n=0;n<h;++n) 37 for(int m=0;m<w;++m) 38 if(grid[n][m]==1) 39 return -1; 40 return time; 41 } 42 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/CHAHA123/p/10736353.html

總結(jié)

以上是生活随笔為你收集整理的leetcode 994.腐烂的橘子的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。