// 演算法與 C 版完全相同:對每層攤平 → 用 k % L 做循環位移 → 順時針寫回。
// Same algorithm as the C version: flatten each layer, shift by k % L, write back clockwise.
// 這裡用 std::vector 取代手動 malloc/free,讓程式更短也更安全。
// Here we use std::vector instead of manual malloc/free for safer, terser code.

#include <vector>   // std::vector,自動管理記憶體的動態陣列 / dynamic array w/ auto memory mgmt
using std::vector;

class Solution {
public:
    vector<vector<int>> rotateGrid(vector<vector<int>>& grid, int k) {
        int m = grid.size();           // 列數 / row count
        int n = grid[0].size();        // 行數 / column count
        int layers = std::min(m, n) / 2;  // 層數 / number of layers

        for (int d = 0; d < layers; ++d) {
            // 當前層的四個邊界 / four boundaries of layer d
            int top = d, bottom = m - 1 - d;
            int left = d, right = n - 1 - d;
            int L = 2 * (bottom - top) + 2 * (right - left);  // 周長 / perimeter

            // vector<int> 是 STL 動態陣列;reserve 預先配置容量,避免多次擴容。
            // vector<int> is the STL dynamic array; reserve preallocates capacity.
            vector<int> arr;
            arr.reserve(L);

            // ---- 攤平:順時針把這一層 push 進 arr ----
            // ---- Flatten the ring clockwise via push_back ----
            for (int j = left; j <= right; ++j)      arr.push_back(grid[top][j]);
            for (int i = top + 1; i <= bottom; ++i)  arr.push_back(grid[i][right]);
            for (int j = right - 1; j >= left; --j)  arr.push_back(grid[bottom][j]);
            for (int i = bottom - 1; i > top; --i)   arr.push_back(grid[i][left]);

            int kk = k % L;   // 有效旋轉次數 / effective shift

            // ---- 順時針寫回,讀位移後的索引 ----
            // ---- Walk the same clockwise path and read shifted positions ----
            int idx = 0;
            for (int j = left; j <= right; ++j)
                grid[top][j]    = arr[(idx++ + kk) % L];
            for (int i = top + 1; i <= bottom; ++i)
                grid[i][right]  = arr[(idx++ + kk) % L];
            for (int j = right - 1; j >= left; --j)
                grid[bottom][j] = arr[(idx++ + kk) % L];
            for (int i = bottom - 1; i > top; --i)
                grid[i][left]   = arr[(idx++ + kk) % L];
            // 迴圈結束,arr 自動被解構釋放;不需要手動 free。
            // arr is destroyed automatically at scope exit — no manual free required.
        }

        return grid;   // 已就地修改,直接回傳 / mutated in place, return as-is
    }
};