# 54. Spiral Matrix 螺旋矩阵

@TOC

## # 题目描述

Given a matrix of `m x n` elements (m rows, n columns), return all elements of the matrix in spiral order.

Example 1:

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

Example 2:

``````Input:
[
[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]
``````

## # 解题方法

### # 维护四个边界和运动方向

python代码如下，核心是每次遇到新的边界时，顺时针修改移动方向，并且将老边界内移。

``````class Solution(object):
def spiralOrder(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[int]
"""
if not matrix or not matrix[0]: return []
M, N = len(matrix), len(matrix[0])
left, right, up, down = 0, N - 1, 0, M - 1
res = []
x, y = 0, 0
dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
cur_d = 0
while len(res) != M * N:
res.append(matrix[x][y])
if cur_d == 0 and y == right:
cur_d += 1
up += 1
elif cur_d == 1 and x == down:
cur_d += 1
right -= 1
elif cur_d == 2 and y == left:
cur_d += 1
down -= 1
elif cur_d == 3 and x == up:
cur_d += 1
left += 1
cur_d %= 4
x += dirs[cur_d][0]
y += dirs[cur_d][1]
return res
``````

### # 保存已经走过的位置

``````class Solution(object):
def spiralOrder(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[int]
"""
if not matrix or not matrix[0]: return []
m, n = len(matrix), len(matrix[0])
visited = [[0] * n for _ in range(m)]
res = []
self.row, self.col = 0, 0
def spiral():
move = False
while self.col < n and not visited[self.row][self.col]:
res.append(matrix[self.row][self.col])
visited[self.row][self.col] = 1
self.col += 1
move = True
self.col -= 1
self.row += 1
while self.row < m and not visited[self.row][self.col]:
res.append(matrix[self.row][self.col])
visited[self.row][self.col] = 1
self.row += 1
move = True
self.row -= 1
self.col -= 1
while self.col >= 0  and not visited[self.row][self.col]:
res.append(matrix[self.row][self.col])
visited[self.row][self.col] = 1
self.col -= 1
move = True
self.col += 1
self.row -= 1
while self.row >= 0 and not visited[self.row][self.col]:
res.append(matrix[self.row][self.col])
visited[self.row][self.col] = 1
self.row -= 1
move = True
self.row += 1
self.col += 1
if move:
spiral()
spiral()
return res
``````

## # 日期

2018 年 3 月 13 日 2019 年 9 月 13 日 —— 一年半后的做法明显变得简单了~