// 演算法 / Algorithm:
// 與 C 版相同：第一行存「列要清」的旗標、第一列存「行要清」的旗標，
// 另用一個 bool 記第一列本身，達成 O(1) 額外空間。
// Same as C: first row = column-flags, first column = row-flags, plus one
// bool for the first column itself → O(1) extra space.

class Solution {
public:
    // vector<vector<int>>& 是「二維向量的參考」/ a reference to a 2D vector.
    // 用 & 代表直接改原矩陣，不複製 / the & means we modify the original in place, no copy.
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();        // 行數 / number of rows (.size() gives element count)
        int n = matrix[0].size();     // 列數 / number of columns

        // 記第一列原本是否含 0 / does the first column originally contain a 0?
        bool firstColZero = false;

        // 第一步：單獨檢查第一列（它與第一行共用 matrix[0][0]）。
        // Step 1: check the first column separately (it shares matrix[0][0] with the first row).
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) firstColZero = true;  // 標記稍後要清第一列 / clear col 0 later
        }

        // 第二步：掃描第一列以外的格子，把 0 的資訊寫進標記行/列。
        // Step 2: scan all cells except column 0, recording zeros into the flag row/column.
        for (int i = 0; i < m; i++) {
            for (int j = 1; j < n; j++) {       // j 從 1 開始跳過第一列 / start at 1 to skip column 0
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;           // 行標記 / row-flag
                    matrix[0][j] = 0;           // 列標記 / column-flag
                }
            }
        }

        // 第三步：依標記回填內部格子（從 1,1 開始，保留標記不被覆蓋）。
        // Step 3: apply flags to inner cells (start at 1,1 so flags aren't overwritten yet).
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                // 此行或此列被標記則設 0 / zero if this row or column was flagged.
                if (matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;
            }
        }

        // 第四步：最後處理第一行 / Step 4: handle the first row last.
        if (matrix[0][0] == 0) {
            for (int j = 0; j < n; j++) matrix[0][j] = 0;  // 整行設 0 / zero the whole first row
        }

        // 第五步：依 firstColZero 處理第一列 / Step 5: clear the first column if flagged.
        if (firstColZero) {
            for (int i = 0; i < m; i++) matrix[i][0] = 0;  // 整列設 0 / zero the whole first column
        }
    }
};