59.Spiral Matrix II

Tags: Medium Array

Links: https://leetcode.com/problems/spiral-matrix-ii/

---

Given a positive integer n, generate a square matrix filled with elements from 1 to *n*2 in spiral order.

Example:

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

---

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        vector<vector<int>> res(n, vector<int>(n));
        vector<vector<bool>> used(n, vector<bool>(n, false));
        int cnt = 0;
        int row = 0, col = 0;
        int direction = 0;
        int total = n * n;
        while (cnt < total) {
            ++cnt;
            res[row][col] = cnt;
            used[row][col] = true;
            while (cnt < total) {
                if (direction == 0) {
                    if (col + 1 < n && !used[row][col + 1]) {
                        ++col; break;
                    }
                    else direction = (direction + 1) % 4;
                }
                if (direction == 1) {
                    if (row + 1 < n && !used[row + 1][col]) {
                        ++row; break;
                    }
                    else direction = (direction + 1) % 4;
                }
                if (direction == 2) {
                    if (col - 1 >= 0 && !used[row][col - 1]) {
                        --col; break;
                    }
                    else direction = (direction + 1) % 4;
                }
                if (direction == 3) {
                    if (row - 1 >= 0 && !used[row - 1][col]) {
                        --row; break;
                    }
                    else direction = (direction + 1) % 4;
                }
            }
        }
        return res;
    }
};

基本上就是按照54题的思路的延申，只是这次不能在原数据修改了，需要新建一个数组记录位置是否被使用过。