题解 | #牛群避免水洼#

大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

这道题目考察的知识点是数组的遍历和原地算法的实现。

步骤 1:

首先，我们需要理解题目的要求。题目给出了一个 m × n 大小的矩阵，其中某些位置表示水洼。牛群不愿意靠近水洼所在行或列的位置。我们的任务是找出哪些位置的草地不会被牛吃掉，并使用原地算法修改矩阵。

步骤 2:

我们可以使用两个辅助数组rowFlag和colFlag，长度分别为m和n，来记录水洼所在的行和列。初始时，这两个数组都为false。

步骤 3:

遍历整个矩阵，当遇到水洼时，将对应行和列的标记数组元素设为true。这样，我们就可以通过辅助数组记录水洼的位置，而不需要在每个位置都进行遍历和标记。

步骤 4:

再次遍历整个矩阵，当某个位置的行或列被标记为true时，将该位置的元素设为-1。

综上所述，我们使用两个辅助数组来记录水洼的行和列，通过两次遍历实现原地算法。通过上述分析，我们可以编写出对应的C++代码来实现题目要求。

本题解析所用的编程语言是C++。

以下是完整的C++代码，包括思考过程的注释：

class Solution {
public:
    vector<vector<int>> avoidPuddles(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();

        vector<bool> rowFlag(m, false); // 记录水洼所在的行
        vector<bool> colFlag(n, false); // 记录水洼所在的列

        // 遍历矩阵，记录水洼所在的行和列
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    rowFlag[i] = true;
                    colFlag[j] = true;
                }
            }
        }

        // 标记未被牛吃掉的草地
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (rowFlag[i] || colFlag[j]) {
                    matrix[i][j] = -1;
                } 
            }
        }

        return matrix;
    }
};