LeetCode 994. 腐烂的橘子

798236606

传送门：https://leetcode-cn.com/problems/rotting-oranges/

BFS

1. class Solution {
   
2. public:
   
3.     struct Pos{
   
4.         int x, y;
   
5.     };
   
6. 
   
7.     int good = 0;
   
8.     bool vis[15][15] = {false};
   
9.     queue<Pos> q;
   
10. 
    
11.     void turn_bad(int x, int y)
    
12.     {
    
13.         q.push({x, y});
    
14.         vis[x][y] = true;   
    
15.         --good;   
    
16.     }
    
17. 
    
18.     int orangesRotting(vector<vector<int>>& grid) {
    
19. 
    
20. 
    
21.         int r = grid.size(), c = grid[0].size();
    
22. 
    
23. 
    
24.         for (int i = 0; i < r; ++i)
    
25.         {
    
26.             for (int j = 0; j < c; ++j)
    
27.             {
    
28.                 if (grid[i][j] == 2)
    
29.                 {
    
30.                     q.push({i, j});
    
31.                     vis[i][j] = true;
    
32.                 }
    
33. 
    
34.                 if (grid[i][j] == 1) ++good;         
    
35.             }
    
36.         }
    
37. 
    
38.         if (!good) return 0;
    
39. 
    
40.         int t = 0;
    
41.         while (int k = q.size())
    
42.         {
    
43.             if (!good) return t;
    
44. 
    
45.             while (k--)
    
46.             {
    
47.                 Pos p = q.front();
    
48.                 q.pop();
    
49. 
    
50.                 if (p.x > 0     && !vis[p.x - 1][p.y] && grid[p.x - 1][p.y] == 1) turn_bad(p.x - 1, p.y);
    
51.                 if (p.x < r - 1 && !vis[p.x + 1][p.y] && grid[p.x + 1][p.y] == 1) turn_bad(p.x + 1, p.y);
    
52.                 if (p.y > 0     && !vis[p.x][p.y - 1] && grid[p.x][p.y - 1] == 1) turn_bad(p.x, p.y - 1);
    
53.                 if (p.y < c - 1 && !vis[p.x][p.y + 1] && grid[p.x][p.y + 1] == 1) turn_bad(p.x, p.y + 1);
    
54.             }
    
55. 
    
56.             ++t;
    
57.         }      
    
58. 
    
59.         return -1;
    
60.     }
    
61. };

复制代码