54.螺旋矩阵.md

// 螺旋矩阵1，此题较难，比起螺旋矩阵2更难处理，这是比较巧妙的民间解法，应该留有印象。
// 对于更下面的2个解法，思路没有全部理通，借助了螺旋矩阵2的写法，仅当参考。

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        // 装结果的res。
        vector<int> res;

        // 初始化上界u、下界d、左界l、右界r。
        int u = 0;
        int d = matrix.size() - 1;
        int l = 0;
        int r = matrix[0].size() - 1;

        // 进入循环
        while (true) {
            // 基于左上角，从左往右遍历，依次res装入遍历结果。
            for (int i = l; i <= r; i++) res.push_back(matrix[u][i]);
            // 遍历完成后，上界u++，如果已经大于下界d，则跳出循环，表明全部处理完成。
            // 极限条件是，此时还剩一行，u=d，从左往右遍历完后，u>d，跳出循环，全部处理完成。
            if (++u > d) break;
            // 基于右上角，从上往下遍历，依次res装入遍历结果。
            for (int i = u; i <= d; i++) res.push_back(matrix[i][r]);
            // 遍历完成后，右界r--，如果已经小于左界l，则跳出循环，表明全部处理完成，同上，下面也类似。
            if (--r < l) break;
            for (int i = r; i >= l; i--) res.push_back(matrix[d][i]);
            if (--d < u) break;
            for (int i = d; i >=u; i--) res.push_back(matrix[i][l]);
            if (++l > r) break;
        }

        return res;
    }
};

/* class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();

        if (m == 1 && n == 1) {
            return {matrix[0][0]};
        }

        int board_start_x = 0;
        int board_start_y = 0;

        int board_end_x = m - 1;
        int board_end_y = n;

        int start_x = 0;
        int start_y = 0;

        vector<int> res;

        cout<<"hello"<<endl;      

        int offset = 1;

        bool is_left_single = true;
        while (true) {
            int i = start_x;
            int j = start_y;

            board_start_y = start_y + n - offset - 1;
            board_start_x = start_x + m - offset - 1;

            for (j = start_y; j <= board_start_y; j++) {
                res.push_back(matrix[i][j]);
            }
            for (i = start_x; i <= board_start_x; i++) {
                res.push_back(matrix[i][j]);
            }
            for (; j > start_y; j--) {
                res.push_back(matrix[i][j]);
            }
            for (; i > start_x; i--) {
                res.push_back(matrix[i][j]);
            }

            start_x++;
            start_y++;
            offset += 2;

            if ((start_y > start_y + n - offset - 1) && (start_x > start_x + m - offset - 1)) {
                if (is_left_single && start_x < m && start_y < n) {
                    res.push_back(matrix[start_x][start_y]);
                }
                break;
            } else {
                is_left_single = false;
            }
        }
        return res;
    }
}; */

/* class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int x = 0;
        int y = 0;

        int m = matrix.size();
        int n = matrix[0].size();

        int board_start_x = 0;
        int board_start_y = 0;

        int board_end_x = m - 1;
        int board_end_y = n;

        int start_x = 0;
        int start_y = 0;

        vector<int> res;

        cout<<"hello"<<endl;      

        while (true) {
            x = start_x;
            y = start_y;
            res.push_back(matrix[x][y]);

            while (board_start_y < board_end_y && board_start_y <= y && y <= board_end_y) {
                y++;
                res.push_back(matrix[x][y]);
            }
            while (board_start_x < board_end_x && board_start_x <= x && x <= board_end_x) {
                x++;
                res.push_back(matrix[x][y]);
            }
            while (board_start_y < board_end_y && board_start_y <= y && y <= board_end_y) {
                y--;
                res.push_back(matrix[x][y]);
            }
            while (board_start_x < board_end_x && board_start_x < x && x <= board_end_x) {
                x--;
                res.push_back(matrix[x][y]);
            }

            board_start_x++;
            board_start_y++;
            board_end_x--;
            board_end_y--;

            for (auto &v:res) {
                cout<<v<<endl;
            }

            if (!(board_start_x <= board_end_x || board_start_y <= board_end_y)) {
                break;
            }

            start_x++;
            start_y++;
        }
        return res;
    }
}; */