题解 | #疯牛病I#
疯牛病I
https://www.nowcoder.com/practice/2066902a557647ce8e85c9d2d5874086
考察的知识点:多维数组、队列;
解答方法分析:
- 创建一个空的有序列表queue,用来存储待传播的感染牛位置。
- 遍历二维数组pasture,找出初始的感染牛位置,将这些位置依插入到有序列表queue中。
- 循环执行以下步骤,直到有序列表queue为空或者传染的次数达到上限k:取出有序列表queue中的第一个牛的位置。遍历该牛的四个相邻位置。如果相邻位置合法且为健康牛,则将其感染标记为2,并插入到有序列表queue的合适位置。
- 统计二维数组pasture中健康牛的数量:创建一个整数变量res,初始化为0。遍历二维数组pasture的每个元素:如果元素为健康牛,则将res加1。
- 返回最终剩余的健康牛数量res。
所用编程语言:C++;
完整编程代码:↓
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param pasture int整型vector<vector<>> * @param k int整型 * @return int整型 */ int healthyCows(vector<vector<int> >& pasture, int k) { int m = pasture.size(); int n = pasture[0].size(); queue<pair<int, int>> q; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (pasture[i][j] == 2) { q.push({i, j}); } } } while (!q.empty() && k > 0) { k--; int size = q.size(); for (int i = 0; i < size; i++) { int x = q.front().first; int y = q.front().second; q.pop(); vector<pair<int, int>> directions = {{x - 1, y}, {x + 1, y}, {x, y - 1}, {x, y + 1}}; for (auto& dir : directions) { int newX = dir.first; int newY = dir.second; if (newX >= 0 && newX < m && newY >= 0 && newY < n && pasture[newX][newY] == 1) { pasture[newX][newY] = 2; q.push({newX, newY}); } } } } int res = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (pasture[i][j] == 1) { res++; } } } return res; } };