题目描述

给定一个正整数 $n$，请生成一个矩阵，将1到 $n^2$ 蛇形排列好。

样例

输入：

3

输出：

[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

算法

(循环) $O(n^2)$

我们顺时针定义四个方向：上右下左。
从左上角开始遍历，先往右走，走到不能走为止，然后更改到下个方向，再走到不能走为止，依次类推，遍历 $n^2$ 个格子后停止。

时间复杂度分析：矩阵中每个格子遍历一次，所以总时间复杂度是 $O(n^2)$。

C++ 代码

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n, 0));

        int dx[4] = {-1, 0, 1, 0};
        int dy[4] = {0, 1, 0, -1};

        for (int x = 0, y = 0, i = 0, d = 1; i < n * n; i ++ )
        {
            res[x][y] = i + 1;
            int a = x + dx[d], b = y + dy[d];
            if (a < 0 || a == n || b < 0 || b == n || res[a][b])
            {
                d = (d + 1) % 4;
                a = x + dx[d], b = y + dy[d];
            }
            x = a, y = b;
        }

        return res;
    }
};