54. Spiral Matrix

Input:  matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]

// 演算法 / Algorithm:
// 用 top/bottom/left/right 四條邊界框住未讀區域，每圈依序讀 上排→右行→下排→左行，
// 讀完一條就把該邊界往內收一格，直到邊界交錯為止。
// Frame the unread region with four boundaries; each ring reads top→right→bottom→left,
// shrinking the matching boundary after every pass, until the boundaries cross.

#include <stdlib.h>  // malloc 在這裡宣告 / malloc is declared here

/* LeetCode 給的簽名：matrix 是 int**，matrixSize 是列數 m，
 * matrixColSize[i] 是第 i 列的行數 n，returnSize 要寫回結果長度。
 * LeetCode signature: matrix is int**, matrixSize = m,
 * matrixColSize[i] = n for row i, write the result length into *returnSize. */
int* spiralOrder(int** matrix, int matrixSize, int* matrixColSize, int* returnSize) {
    int m = matrixSize;             // 列數 / number of rows
    int n = matrixColSize[0];       // 行數（每列等長）/ number of columns (all rows equal)

    int total = m * n;              // 元素總數 / total number of elements
    *returnSize = total;            // 透過指標把長度回傳給呼叫者 / report length to caller via pointer

    // 向系統要一塊能裝 total 個 int 的記憶體；回傳的指標就是輸出陣列
    // Ask the OS for room for `total` ints; the returned pointer is our output array
    int* out = (int*)malloc(sizeof(int) * total);

    int k = 0;                      // out 的下一個寫入位置 / next write slot in out

    int top = 0, bottom = m - 1;    // 上下邊界（含端點）/ top & bottom row boundaries (inclusive)
    int left = 0, right = n - 1;    // 左右邊界（含端點）/ left & right column boundaries (inclusive)

    // 只要還有未讀的格子就繼續 / keep going while an unread rectangle still exists
    while (top <= bottom && left <= right) {

        // (1) 沿 top 這一列，由左到右 / top row, left → right
        for (int j = left; j <= right; j++)
            out[k++] = matrix[top][j];   // matrix[top][j] 取第 top 列第 j 行 / cell at row top, col j
        top++;                            // 這一列讀完，邊界下移 / done with this row, move boundary down

        // (2) 沿 right 這一行，由上到下 / right column, top → bottom
        for (int i = top; i <= bottom; i++)
            out[k++] = matrix[i][right];
        right--;                          // 最右行讀完，邊界左移 / done, move boundary left

        // (3) 沿 bottom 這一列，由右到左；先確認還有列可讀，避免單列重讀
        //     bottom row, right → left; guard against re-reading a single leftover row
        if (top <= bottom) {
            for (int j = right; j >= left; j--)
                out[k++] = matrix[bottom][j];
            bottom--;                     // 最底列讀完，邊界上移 / move boundary up
        }

        // (4) 沿 left 這一行，由下到上；先確認還有行可讀，避免單行重讀
        //     left column, bottom → top; guard against re-reading a single leftover column
        if (left <= right) {
            for (int i = bottom; i >= top; i--)
                out[k++] = matrix[i][left];
            left++;                       // 最左行讀完，邊界右移 / move boundary right
        }
    }

    return out;   // 回傳結果陣列；LeetCode 會負責 free / return result; LeetCode frees it
}

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