Medium
Related Topics: Array / Matrix / Simulation
LeetCode Source

解題想法

首先設定每次尋訪的方向在 vector<vector<int>> directions 裡頭

每次執行 2 次時，會增加走訪的長度 steps

接著就是從 rStart 和 cStart 開始尋訪

當 [rStart, cStart] 有在規範的範圍內時

紀錄 count 跟將此位置存在 vector<vector<int>> res 裡頭

持續紀錄直到 count 跟 row * cols 一樣時

最後回傳 res

Complexity

Time Complexity: O(rows * cols)
Space Complexity: O(rows * cols)

Python

class Solution:
    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:
        res = []
        count = 0
        steps = 1
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        d = 0 

        res.append([rStart, cStart])
        count += 1

        while count < rows * cols:
            for _ in range(2):
                for _ in range(steps):
                    rStart += directions[d][0]
                    cStart += directions[d][1]
                    if 0 <= rStart < rows and 0 <= cStart < cols:
                        res.append([rStart, cStart])
                        count += 1
                d = (d + 1) % 4
            steps += 1

        return res

C++

class Solution {
public:
    vector<vector<int>> spiralMatrixIII(int rows, int cols, int rStart, int cStart) {
        vector<vector<int>> res;
        int count = 0, steps = 1, d = 0;
        vector<vector<int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

        res.push_back({rStart, cStart});
        count += 1;

        while (count < rows * cols) {
            for (int i = 0; i < 2; i++) {
                for (int i = 0; i < steps; i++) {
                    rStart += directions[d][0];
                    cStart += directions[d][1];
                    if (rStart >= 0 && rStart < rows && cStart >= 0 && cStart < cols) {
                        res.push_back({rStart, cStart});
                        count += 1;
                    }
                }
                d = (d + 1) % 4;
            }
            steps += 1;
        }

        return res;
    }
};