题目来源:https://leetcode.com/problems/cousins-in-binary-tree/description/
标记难度:Easy
提交次数:1/1
代码效率:12ms
题意
在一个四连通图上有若干个橘子,其中有一些是烂的,烂橘子每秒都会向四连通的橘子扩散,问经过多少秒,所有的橘子会烂掉?
分析
前几天在CF上做过一道有点类似的题(1105D,也是BFS分次扩展,当时虽然过了pretest,却因为每次扩展的结点过多且queue
初始化过慢超时了。所以我就学到了一个道理:在这种情况下注意到底应该扩展哪些结点。不过这道题其实没有这个必要……
考虑到这一点,不如直接用vector
代替queue
。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43
| class Solution { public: int orangesRotting(vector<vector<int>>& grid) { vector<pair<int, int>> q; int orangeCnt = 0; int n = grid.size(), m = grid[0].size(); int mx[4] = {0, 0, 1, -1}; int my[4] = {1, -1, 0, 0}; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (grid[i][j] != 0) orangeCnt++; if (grid[i][j] == 2) q.emplace_back(i, j); } } if (q.size() == orangeCnt) return 0; if (q.size() == 0) return -1; int lastEnd = 0, lastSize = q.size(); for (int i = 1; ; i++) { for (int j = lastEnd; j < lastSize; j++) { int x = q[j].first, y = q[j].second; for (int k = 0; k < 4; k++) { int nx = x + mx[k], ny = y + my[k]; if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; if (grid[nx][ny] == 1) { grid[nx][ny] = 2; q.emplace_back(nx, ny); } } } if (lastSize == q.size()) return -1; if (q.size() == orangeCnt) return i; lastEnd = lastSize; lastSize = q.size(); } return 0; } };
|