73. 矩阵置零

class Solution {
public:
  void setZeroes(vector<vector<int>>& matrix) {
    int M = matrix.size();
    int N = matrix.front().size();
    vector<int> RowsToClear(M, 0);
    vector<int> ColsToClear(N, 0);
    // Mark.
    for (int y = 0; y < M; ++y) {
      for (int x = 0; x < N; ++x) {
        if (matrix[y][x] != 0)
          continue;
        RowsToClear[y] = 1;
        ColsToClear[x] = 1;
      }
    }
    // Clear.
    for (int y = 0; y < M; ++y) {
      if (!RowsToClear[y])
        continue;
      for (int x = 0; x < N; ++x)
        matrix[y][x] = 0;
    }
    for (int x = 0; x < N; ++x) {
      if (!ColsToClear[x])
        continue;
      for (int y = 0; y < M; ++y)
        matrix[y][x] = 0;
    }
  }
};

class Solution {
public:
  void setZeroes(vector<vector<int>>& matrix) {
    int M = matrix.size();
    int N = matrix.front().size();
    bool ClearFirstRow = false;
    bool ClearFirstCol = false;
    // CHECK if first column/row needs to be cleared. Notice that we won't
    // change the first column/row at this time. This can avoid us dealing with
    // corner cases where we might need to check if x == 0 or y == 0.
    for (int y = 0; y < M; ++y) {
      if (matrix[y][0] == 0) {
        ClearFirstCol = true;
        break;
      }
    }
    for (int x = 0; x < N; ++x) {
      if (matrix[0][x] == 0) {
        ClearFirstRow = true;
        break;
      }
    }
    // CHECK and MARK remaining cols and rows. Mind that the clear flag is ZERO
    // instead of ONE. Since zeroes are all the same, while non-zeros are not.
    for (int y = 1; y < M; ++y) {
      for (int x = 1; x < N; ++x) {
        if (matrix[y][x] == 0)
          matrix[y][0] = matrix[0][x] = 0;
      }
    }
    // Clear remaining columns and rows.
    for (int y = 1; y < M; ++y) {
      for (int x = 1; x < N; ++x) {
        if (!matrix[y][0] || !matrix[0][x])
          matrix[y][x] = 0;
      }
    }
    // Lastly, clear first column/row.
    if (ClearFirstCol) {
      for (int y = 0; y < M; ++y)
        matrix[y][0] = 0;
    }
    if (ClearFirstRow) {
      for (int x = 0; x < N; ++x)
        matrix[0][x] = 0;
    }
  }
};