題目

該題值推薦用bfs，因?yàn)槭且粚右粚拥母腥?，而不是一條線走到底的那種，所以深度優(yōu)先搜索不適合

方法一：bfs+層序遍歷

廣度優(yōu)先搜索，就是從起點(diǎn)出發(fā)，每次都嘗試訪問同一層的節(jié)點(diǎn)，如果同一層都訪問完了，再訪問下一層，最后廣度優(yōu)先搜索找到的路徑就是從起點(diǎn)開始的最短合法路徑。

在該題：假設(shè)圖中只有一個腐爛的橘子，它每分鐘向外拓展，腐爛上下左右相鄰的新鮮橘子，那么下一分鐘，就是這些被腐爛的橘子再向外拓展腐爛相鄰的新鮮橘子，這與廣度優(yōu)先搜索的過程均一一對應(yīng)，上下左右相鄰的新鮮橘子就是該腐爛橘子嘗試訪問的同一層的節(jié)點(diǎn)，路徑長度就是新鮮橘子被腐爛的時間。
文章來源地址http://www.zghlxwxcb.cn/news/detail-693735.html

class Solution {
// 方法一 : bfs   
    int m = 0;
    int n = 0;//  全局 格子寬度和長度
    int minute = 0;//全局  最小分鐘數(shù)
    int fulash = 0;// 記錄1的個數(shù)
    public int orangesRotting(int[][] grid) {
       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++){
           if(grid[i][j] == 1 ) fulash++;//記錄新鮮橘子的個數(shù)
           if(grid[i][j] == 2 ){
               grid[i][j] = 2;
               queue.offer(new int[]{i,j});//將壞橘子坐標(biāo)數(shù)組 存入隊(duì)列
               
           }
       }
        //層序遍歷
          while(!queue.isEmpty() && fulash > 0){// 當(dāng)隊(duì)列空了 或者 沒有新鮮橘子了，停止循環(huán)
                    int size = queue.size();
                    minute++;// 一層一層的傳染，每傳染一層，時間+1
                for(int i = 0 ; i<size ;i++){
                   int[] mid = queue.poll();
                   int x = mid[0];
                   int y = mid[1];
                   //上
                   if(x+1 < m && grid[x+1][y]== 1 ){
                       fulash--; // 每傳染一個，更新新鮮橘子的數(shù)量
                      grid[x+1][y] = 2;//將新鮮果子感染
                      queue.offer(new int[]{x+1,y});//將感染的果子加入隊(duì)列，進(jìn)行下一層的處理

                   }
                   //下
                   if(x-1 >=0 && grid[x-1][y]== 1 ){
                         fulash--;
                       grid[x-1][y] = 2;
                       queue.offer(new int[]{x-1,y});
                        
                   }
                   //右
                   if(y+1 < n && grid[x][y+1]== 1 ){
                         fulash--;
                       grid[x][y+1] = 2;
                       queue.offer(new int[]{x,y+1});
                        
                   }
                   //左
                   if(y-1 >=0 && grid[x][y-1]== 1 ){
                         fulash--;
                       grid[x][y-1] = 2;
                       queue.offer(new int[]{x,y-1});  
                   }
            }

                
        }

        if(fulash > 0) return -1;//若還有新鮮橘子  則返回-1
        else  return minute;//無新鮮橘子  則返回minute
    }

}

到了這里，關(guān)于【LeetCode-中等題】994. 腐爛的橘子的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！