/*
 * 演算法 / 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
    }
};