Spiral Matrix III

https://leetcode.com/problems/spiral-matrix-iii/description/

Thoughts

可越界旋转矩阵，按旋转顺序记录所有落在界内把格子的值。因为可越界，边界收缩规律不再明显，因此模拟走格。经观察，会向右和和向下走k步，然后左和上k + 1步，再右和下k+2步。。即会在两个方向走同一步数次，然后步数再加一。

Code

class Solution {
public:
    vector<vector<int>> spiralMatrixIII(int R, int C, int r0, int c0) {
        vector<vector<int>> res(R * C, vector<int>(2));
        int dir[][2]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int r = r0, c = c0, di = 0, step = 1;
        for (int i = 0; i < R * C;) {
            for (int j = 0; j < 2; ++j) {
                for (int k = 0; k < step; ++k) {
                    if (r >= 0 && r < R && c >= 0 && c < C) {
                        res[i++] = {r, c};
                    }
                    r += dir[di][0];
                    c += dir[di][1];
                }
                di = (di + 1) % 4;
            }
            ++step;
        }

        return res;
    }
};

Analysis

Time Complexity: O((\max(R, C))^2)O((max(R,C))

​2

​​ ). Potentially, our walk needs to spiral until we move R in one direction, and CC in another direction, so as to reach every cell of the grid.

1 + 1 + 2 + 2 + 3 + ... + max(R/C) = O(max(R, C)^2)