※ 引述《smart0eddie (smart0eddie)》之铭言：
: 2024-08-08
: 885. Spiral Matrix III
: You start at the cell (rStart, cStart) of an rows x cols grid facing east.
: The northwest corner is at the first row and column in the grid, and the
: southeast corner is at the last row and column.
: You will walk in a clockwise spiral shape to visit every position in this
: grid. Whenever you move outside the grid's boundary, we continue our walk
: outside the grid (but may return to the grid boundary later.). Eventually, we
: reach all rows * cols spaces of the grid.
: Return an array of coordinates representing the positions of the grid in the
: order you visited them.
: 好像只能照着刻然后一格一格走塞进去欸?
: 在外面的时候可能可以用数学解跳过吧
: 可是感觉好麻烦
: 基本上萝悬是从最小圈开始往前走一格以后转弯
: 每转弯两次会碰到上一圈的 要多走一格
: class Solution {
: public:
: vector<vector<int>> spiralMatrixIII(int rows, int cols, int rStart, int
: cStart) {
: const vector<vector<int>> ds = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
: const int grids_number = rows * cols;
: vector<vector<int>> results;
: int max_step = 1;
: int dir = 0;
: int step = 0;
: int x = cStart, y = rStart;
: while (results.size() < grids_number) {
: if (isInside(x, y, rows, cols)) {
: results.push_back({y, x});
: }
: x += ds[dir][0];
: y += ds[dir][1];
: step++;
: if (step == max_step) {
: step = 0;
: dir = (dir + 1) % 4;
: if (!(dir % 2)) {
: max_step++;
: }
: }
: }
: return results;
: }
: private:
: inline bool isInside(const int x, const int y, const int rows, const int
: cols) {
: return x >=0 && x < cols && y >= 0 && y < rows;
: }
: };
思路:
顺时钟走就每走两个方向就多走一步 11,22,33...... 以此类推
然后要走完整个矩阵 所以先算矩阵大小
后面就照着模拟 假如所在位子在矩阵范围内 矩阵大小-1
最后矩阵大小归零代表走完矩阵 回传结果end
Python Code:
class Solution:
def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int)
-> List[List[int]]:
dx = [1,0,-1,0]
dy = [0,1,0,-1]
result = [[rStart,cStart]]
total = (rows * cols)-1
direction = 0
time = 1
while total:
for _ in range(time):
cStart += dx[direction]
rStart += dy[direction]
if rStart >= 0 and cStart >= 0 and cStart < cols and rStart <
rows:
total -= 1
result.append([rStart,cStart])
if (direction % 2) == 1:
time += 1
direction = (direction + 1) % 4
return result