# LeetCode Medium 54. Spiral Matrix

tags: leetcode

問題

• Explore
• Problems

アイデア

｢m x n行列が与えられたとき，右回りに螺旋状に動いた際に通る要素の配列にして返せ｣という問題です．

螺旋状に動くとは左上→右上→右下→左下→...のように動くことです(直感的には)．

これを如何に実直に実装すればいいのかを考えます．

解法

• visitedというbooleanの値の配列の配列を用意して，この配列を使って一度通ったかどうかを確認します．

計算量

• 時間計算量
  • $O(NM)$
• 空間計算量
  • $O(NM)$

Python

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix:
            return []
    
        max_row, max_col = len(matrix), len(matrix[0])
        visited = [[False] * max_col for _ in matrix]
        res = []
        dir_row = [0, 1, 0, -1]
        dir_col = [1, 0, -1, 0]
        row = col = di = 0
        for _ in range(max_row * max_col):
            res.append(matrix[row][col])
            visited[row][col] = True
            next_row, next_col = row + dir_r[di], col + dir_c[di]
            if 0 <= next_row < max_row and 0 <= next_col < max_col and not visited[next_row][next_col]:
                row, col = next_row, next_col
            else:
                di = (di + 1) % 4
                row, col = row + dir_r[di], col + dir_col[di]
        return res