C++刷LeetCode（994. 腐烂的橘子）【广度优先搜索】

糖逗

题目描述：

1. 在给定的网格中，每个单元格可以有以下三个值之一：
   
2. 
   
3. 值 0 代表空单元格；
   
4. 值 1 代表新鲜橘子；
   
5. 值 2 代表腐烂的橘子。
   
6. 每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。
   
7. 
   
8. 返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。
   
9. 
   
10. 
    
11. 
    
12. 示例 1：
    
13. 
    
14. 
    
15. 
    
16. 输入：[[2,1,1],[1,1,0],[0,1,1]]
    
17. 输出：4
    
18. 示例 2：
    
19. 
    
20. 输入：[[2,1,1],[0,1,1],[1,0,1]]
    
21. 输出：-1
    
22. 解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个正向上。
    
23. 示例 3：
    
24. 
    
25. 输入：[[0,2]]
    
26. 输出：0
    
27. 解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。
    
28. 
    
29. 
    
30. 提示：
    
31. 
    
32. 1 <= grid.length <= 10
    
33. 1 <= grid[0].length <= 10
    
34. grid[i][j] 仅为 0、1 或 2

复制代码

1. class Solution {
   
2. public:
   
3.     int orangesRotting(vector<vector<int>>& grid) {
   
4.         //广度优先搜索
   
5.         queue<vector<int> > store;
   
6.         int len1 = grid.size(), len2 = grid[0].size();
   
7.         if(len1 == 1 && len2 == 1){
   
8.             if(grid[0][0] == 1)return -1;
   
9.             else if(grid[0][0] == 0 || grid[0][0] == 2) return 0;
   
10.         }
    
11.         int fresh = 0;
    
12.         for(int i = 0 ; i < len1; i++){
    
13.             for(int j = 0; j < len2; j++){
    
14.                 if(grid[i][j] == 2)store.push({i, j});
    
15.                 else if(grid[i][j] == 1)fresh++;
    
16.             }
    
17.         }
    
18.         int res = -1;
    
19.         int total = 0;
    
20.         while(!store.empty()){
    
21.             int len = store.size();
    
22.             res++;
    
23.             for(int i = 0; i < len; i++){
    
24.                 int x = store.front()[0];
    
25.                 int y = store.front()[1];
    
26.                 store.pop();
    
27.                 if(x - 1 >= 0 && grid[x - 1][y] == 1){
    
28.                     store.push({x-1, y});
    
29.                     grid[x - 1][y] = 2;
    
30.                     total++;
    
31.                 }
    
32.                 if(x + 1 < len1 && grid[x + 1][y] == 1){
    
33.                     store.push({x+1, y});
    
34.                     grid[x + 1][y] = 2;
    
35.                     total++;
    
36.                 }
    
37.                 if(y - 1 >= 0 && grid[x][y - 1] == 1){
    
38.                     store.push({x, y - 1});
    
39.                     grid[x][y-1] = 2;
    
40.                     total++;
    
41.                 }
    
42.                 if(y + 1 < len2 && grid[x][y + 1] == 1){
    
43.                     store.push({x, y + 1});
    
44.                     grid[x][y+1] = 2;
    
45.                     total++;
    
46.                 }
    
47.             }
    
48.         }
    
49.         if(total != fresh)return -1;
    
50.         return res;
    
51.     }
    
52. };

复制代码

小甲鱼的铁粉

我也想学算法，但是c++还没学

糖逗

小甲鱼的铁粉 发表于 2020-7-6 13:26
我也想学算法，但是c++还没学

什么语言都可以，这个不限制语言。

永恒的蓝色梦想

小甲鱼的铁粉 发表于 2020-7-6 13:26
我也想学算法，但是c++还没学

拿什么语言不能学算法

小甲鱼的铁粉

永恒的蓝色梦想 发表于 2020-7-6 15:20
拿什么语言不能学算法

主要是想学算法去竞赛呢，好像是c++竞赛最多