// 演算法 / Algorithm:
// 與 C 版相同：四條邊界 top/bottom/left/right 框住未讀區域，
// 每圈讀 上→右→下→左 並把對應邊界往內收，直到邊界交錯。
// Same as the C version: four boundaries enclose the unread region; each ring reads
// top→right→bottom→left and shrinks the matching boundary until they cross.

#include <vector>
using namespace std;

class Solution {
public:
    // vector<vector<int>> 是「裝著 int 向量的向量」，即二維動態陣列
    // vector<vector<int>> is a vector of int-vectors, i.e. a dynamic 2D array
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int m = matrix.size();        // 列數 / number of rows
        int n = matrix[0].size();     // 行數 / number of columns

        vector<int> out;              // 結果向量，會自動成長 / result vector, grows automatically
        out.reserve(m * n);           // 預先配置空間，避免反覆重新配置 / pre-allocate to avoid reallocations

        int top = 0, bottom = m - 1;  // 上下邊界 / top & bottom boundaries (inclusive)
        int left = 0, right = n - 1;  // 左右邊界 / left & right boundaries (inclusive)

        while (top <= bottom && left <= right) {

            // (1) top 列由左到右 / top row, left → right
            for (int j = left; j <= right; ++j)
                out.push_back(matrix[top][j]);   // push_back 把元素加到尾端 / append to the end
            ++top;

            // (2) right 行由上到下 / right column, top → bottom
            for (int i = top; i <= bottom; ++i)
                out.push_back(matrix[i][right]);
            --right;

            // (3) bottom 列由右到左；守門避免單列重讀 / bottom row, guarded against single-row reread
            if (top <= bottom) {
                for (int j = right; j >= left; --j)
                    out.push_back(matrix[bottom][j]);
                --bottom;
            }

            // (4) left 行由下到上；守門避免單行重讀 / left column, guarded against single-col reread
            if (left <= right) {
                for (int i = bottom; i >= top; --i)
                    out.push_back(matrix[i][left]);
                ++left;
            }
        }

        return out;   // 回傳結果 / return the spiral order
    }
};