// 演算法 / Algorithm:
// 用第一行當「列要清零」的標記、第一列當「行要清零」的標記，
// 額外一個變數記第一列本身要不要清零，達到 O(1) 額外空間。
// Use first row as column-flags and first column as row-flags; one extra
// scalar tracks the first column itself. Result: O(1) extra space.

// matrixSize 是行數 m / matrixSize is the number of rows (m).
// matrixColSize[i] 是第 i 行的列數 / matrixColSize[i] is the column count of row i.
void setZeroes(int** matrix, int matrixSize, int* matrixColSize) {
    int m = matrixSize;          // 行數 / number of rows
    int n = matrixColSize[0];    // 列數（每行一樣寬）/ number of columns (rows are uniform)

    // firstColZero 記第一列原本有沒有 0 / does the first column originally contain a 0?
    // 用 int 當布林：0=false, 1=true / use int as a boolean flag.
    int firstColZero = 0;

    // 第一步：單獨檢查第一列，因為它和第一行共用 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++) {        // 走過每一行的第 0 列 / scan column 0 of every row
        if (matrix[i][0] == 0) {         // 若該格是 0 / if this cell is zero
            firstColZero = 1;            // 記住整個第一列稍後要清 / remember to clear column 0 later
        }
    }

    // 第二步：掃描「除第一列外」的所有格子，把 0 的資訊記到第一行/第一列的標記上。
    // Step 2: scan all cells except column 0; record zeros into the flag row/column.
    for (int i = 0; i < m; i++) {            // 每一行 / each row
        for (int j = 1; j < n; j++) {        // 從 j=1 開始，跳過第一列 / start at j=1, skip column 0
            if (matrix[i][j] == 0) {         // 發現一個 0 / found a zero
                matrix[i][0] = 0;            // 行標記：此行要清 / row-flag: this row must be cleared
                matrix[0][j] = 0;            // 列標記：此列要清 / column-flag: this column must be cleared
            }
        }
    }

    // 第三步：根據標記回填內部格子（從第 1 行、第 1 列開始，避免覆蓋標記）。
    // Step 3: use the flags to zero inner cells (start at row 1, col 1 so flags stay intact).
    for (int i = 1; i < m; i++) {            // 從第 1 行開始 / from row 1
        for (int j = 1; j < n; j++) {        // 從第 1 列開始 / from column 1
            // 若此行被標記、或此列被標記，就把這格設 0。
            // If this row or this column was flagged, zero this cell.
            if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                matrix[i][j] = 0;
            }
        }
    }

    // 第四步：最後才處理第一行。matrix[0][0] 同時代表「第一行要不要清」。
    // Step 4: handle the first row last. matrix[0][0] tells us if the first row needs clearing.
    if (matrix[0][0] == 0) {                 // 第一行需要清零 / first row must be zeroed
        for (int j = 0; j < n; j++) {        // 整個第一行設 0 / set entire first row to 0
            matrix[0][j] = 0;
        }
    }

    // 第五步：用先前存的 firstColZero 處理第一列。
    // Step 5: use the saved firstColZero to clear the first column if needed.
    if (firstColZero) {                      // 第一列需要清零 / first column must be zeroed
        for (int i = 0; i < m; i++) {        // 整個第一列設 0 / set entire column 0 to 0
            matrix[i][0] = 0;
        }
    }
}