54.Spiral Matrix
===

###### tags: `Medium`,`Array`,`Matrix`

[54. Spiral Matrix](https://leetcode.com/problems/spiral-matrix/)

### 題目描述

Given an `m x n` `matrix`, return *all elements of the* `matrix` *in spiral order.*

### 範例

**Example 1:**


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

**Example 2:**


Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

**Constraints**:

* `m` == `matrix.length`
* `n` == `matrix[i].length`
* 1 <= `m`, `n` <= 10
* -100 <= `matrix[i][j]` <= 100

### 解答
#### Javascript
思路：每次都把第一排拿出來，然後逆時針旋轉90度，重複到拿完為止。

function spiralOrder(matrix) {
  const result = [];
  while (matrix.length > 0) {
    result.push(...matrix.shift());
    if (matrix.length > 0) {
      matrix = rotate(matrix);
    }
  }

  return result;
}

// 逆時針旋轉90度
function rotate(matrix) {
  const newMatrix = [];
  const yLength = matrix.length;
  const xLength = matrix[0].length;
  for (let y = 0; y < xLength; y++) {
    newMatrix[y] = [];
  }

  for (let y = 0; y < yLength; y++) {
    for (let x = 0; x < xLength; x++) {
      const length = matrix[y].length;
      const rX = y;
      const rY = length - 1 - x;
      newMatrix[rY][rX] = matrix[y][x];
    }
  }

  return newMatrix;
}

> [name=Marsgoat][time=May 9, 2023]

#### Python

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        m, n = len(matrix), len(matrix[0])
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        d = 0
        sx, sy = 0, 0
        res = [matrix[0][0]]
        VISITED = 101
        matrix[0][0] = VISITED

        while len(res) < m * n:
            dx, dy = directions[d % 4]
            nx, ny = sx + dx, sy + dy

            if 0 <= nx < m and 0 <= ny < n and matrix[nx][ny] != VISITED:
                res.append(matrix[nx][ny])
                matrix[nx][ny] = VISITED
                sx, sy = nx, ny
            else:
                d += 1

        return res

> [name=Ron Chen][time=Tue, May 9, 2023]

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        return matrix and matrix[0] + self.spiralOrder(list(map(list, reversed(list(zip(*matrix[1:]))))))

> [name=Yen-Chi Chen][time=Tue, May 9, 2023]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)