/*
 * 演算法 / 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 個字元 + 結尾 '\0' / 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] = '\0';                        // C 字串需要 null 結尾 / null-terminate
        }
    }
    return result;                                         // 交回結果 / return the rotated grid
}