1861. Rotating the Box

Input:  [["#",".","#"]]
Output: [["."],
         ["#"],
         ["#"]]

/*
 * 演算法 / Algorithm:
 * 1. 對每一列由右往左掃，用 write 指針把石頭推到右側 (= 旋轉後的下方)。
 *    Sweep each row right-to-left and push stones rightward (= "down" after rotation).
 * 2. 用公式 rot[i][j] = box[m-1-j][i] 把推完石頭的矩陣順時針旋轉 90°。
 *    Rotate the gravity-applied matrix 90° clockwise via rot[i][j] = box[m-1-j][i].
 * Time: O(m*n), Space: O(m*n) for the output (input is modified in place).
 */

// LeetCode 此題每個格子是長度 1 的字串，所以矩陣型別是 char***
// On LeetCode this problem uses char*** because each cell is a 1-char string
char*** rotateTheBox(
    char*** box,                  // 原矩陣 / input grid, box[i][j] 是一個字串 / a string
    int boxSize,                  // m，列數 / number of rows
    int* boxColSize,              // 每列的長度（都等於 n）/ row lengths (all = n)
    int* returnSize,              // 輸出指標：要寫入結果列數 / pointer to output row count
    int** returnColumnSizes       // 輸出指標：要寫入每列長度的陣列 / pointer to per-row length array
) {
    int m = boxSize;              // m 是原本的列數 / m = rows of input
    int n = boxColSize[0];        // n 是每列的長度 / n = cols of input

    // ---------- Phase 1: 把每列的石頭推到右邊 / push stones right per row ----------
    for (int i = 0; i < m; i++) {                  // 對每一列獨立處理 / each row is independent
        int write = n - 1;                         // 下一顆石頭該放的位置 / slot for next stone
        for (int j = n - 1; j >= 0; j--) {         // 由右往左掃 / scan right-to-left
            char c = box[i][j][0];                 // 取出該格字元 / read the cell's char
            if (c == '*') {                        // 障礙擋住右側 / obstacle blocks the right
                write = j - 1;                     // 新可放位置在障礙左邊 / next slot is left of it
            } else if (c == '#') {                 // 是石頭就要往右掉 / a stone falls right
                box[i][j][0] = '.';                // 原位變空 / vacate old spot
                box[i][write][0] = '#';            // 寫入指針位置 / drop into write slot
                write--;                           // 下一顆石頭再往左堆 / next stone stacks left
            }
            // c == '.' 不用做事 / empty cell needs no action
        }
    }

    // ---------- Phase 2: 順時針旋轉 90° / rotate 90° clockwise ----------
    *returnSize = n;                                       // 旋轉後共 n 列 / output has n rows
    // 配置長度為 n 的「每列長度」陣列 / allocate per-row size array of length n
    *returnColumnSizes = (int*)malloc(sizeof(int) * n);
    // 配置外層指標陣列：n 個 char** / allocate outer array of n row pointers
    char*** result = (char***)malloc(sizeof(char**) * n);

    for (int i = 0; i < n; i++) {                          // 填入每一列 / fill each output row
        (*returnColumnSizes)[i] = m;                       // 每列有 m 個元素 / each row has m cells
        result[i] = (char**)malloc(sizeof(char*) * m);     // 配置這一列的格子陣列 / row of m strings
        for (int j = 0; j < m; j++) {
            // 每格分配 2 bytes：1 個字元 + 結尾 '' / 2 bytes: 1 char + null terminator
            result[i][j] = (char*)malloc(sizeof(char) * 2);
            // 套用旋轉公式 / apply rotation formula:
            // rot[i][j] = box[m-1-j][i]
            result[i][j][0] = box[m - 1 - j][i][0];
            result[i][j][1] = '';                        // C 字串需要 null 結尾 / null-terminate
        }
    }
    return result;                                         // 交回結果 / return the rotated grid
}

/*
 * 演算法 / Algorithm:
 * 1. 對每列由右往左掃，把石頭推到右邊 (旋轉後即落到下方)。
 *    For each row, sweep right-to-left and push stones to the right (== "down" after rotating).
 * 2. 以 rot[i][j] = box[m-1-j][i] 順時針旋轉成 n x m 結果。
 *    Rotate via rot[i][j] = box[m-1-j][i] into an n x m result.
 * Time: O(m*n). Space: O(m*n) for the output.
 */

class Solution {
public:
    // LeetCode 給的型別是 vector<vector<char>>，每格直接是 char
    // LeetCode signature uses vector<vector<char>>; each cell is a plain char
    vector<vector<char>> rotateTheBox(vector<vector<char>>& box) {
        int m = box.size();           // 列數 / number of rows
        int n = box[0].size();        // 行數 / number of columns

        // ---------- Phase 1: 每列把石頭推到右邊 / gravity-right per row ----------
        for (int i = 0; i < m; ++i) {              // 逐列處理 / process each row
            int write = n - 1;                     // 下一個可放石頭的位置 / next free slot
            for (int j = n - 1; j >= 0; --j) {     // 由右往左掃 / right-to-left scan
                if (box[i][j] == '*') {            // 障礙會擋住右側石頭 / obstacle blocks rightward
                    write = j - 1;                 // 新落點在障礙左邊一格 / new slot is left of obstacle
                } else if (box[i][j] == '#') {     // 石頭往右掉到 write 位置 / stone falls to write
                    box[i][j] = '.';               // 原位置清空 / clear original cell
                    box[i][write] = '#';           // 在 write 位置放下石頭 / place stone at write
                    --write;                       // 下顆石頭往左疊 / next stone stacks one to the left
                }
                // '.' 就什麼都不做 / nothing to do for empty cells
            }
        }

        // ---------- Phase 2: 順時針旋轉 / clockwise rotate ----------
        // 用「外圍 vector 大小 n、內層每個 vector 大小 m」的方式建好空矩陣
        // Build an n x m result vector pre-sized to the rotated dimensions
        vector<vector<char>> result(n, vector<char>(m));
        for (int i = 0; i < n; ++i) {              // 走每一個輸出位置 / iterate each output cell
            for (int j = 0; j < m; ++j) {
                // 旋轉公式：新 (i,j) 來自原 (m-1-j, i)
                // Rotation formula: new (i,j) comes from old (m-1-j, i)
                result[i][j] = box[m - 1 - j][i];
            }
        }
        return result;                             // 交回旋轉後矩陣 / return rotated grid
    }
};