54. 螺旋矩阵

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

示例 2：

输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

提示：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/spiral-matrix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

模拟法。

模拟有一个遍历机器人，按照螺旋轨迹（4个方向：向右，向下，向左，向上）每一步一个格子移动（很显然，遍历完矩阵，要移动 m*n 次）。
已经遍历了的格子，我们标记一下，作为转弯的边界条件： visited[row][col] = true。
另外，在第一层遍历的时候，转弯的边界条件是不得超出矩阵的坐标范围，也就是:
0 < row < m
0 < col < n

关于方向向量： direction[4][2]
4个方向：向右，向下，向左，向上
（行下标，列下标）
向右，(0,+1)
向下，(+1,0)
向左，(0,-1)
向上，(-1,0)

代码

class Solution {
    fun spiralOrder(matrix: Array<IntArray>): List<Int> {
        val ans = mutableListOf<Int>()
        val rows = matrix.size
        if (rows == 0) {
            return emptyList()
        }
        val cols = matrix[0].size
        var row = 0
        var col = 0
        val total = rows * cols
        val direction = arrayOf(
            arrayOf(0, 1),  // right, row 不变,col + 1
            arrayOf(1, 0),  // down,  col 不变, row + 1
            arrayOf(0, -1), // left,  row 不变, col - 1
            arrayOf(-1, 0) // up,    col 不变, row - 1
        )

        // 是否已经访问过, 作为转弯的边界条件
        val visited: Array<BooleanArray> = Array(rows) {
            BooleanArray(cols) { false }
        }

        // direction 的下标, 取值为: 0, 1, 2, 3
        var directionIndex = 0

        // visit [ 0 ~ total-1 ] element
        for (i in 0 until total) {

            ans.add(matrix[row][col])
            visited[row][col] = true

            val nextRow = row + direction[directionIndex][0]
            val nextCol = col + direction[directionIndex][1]

            if (shouldTurnDirection(nextRow, nextCol, rows, cols, visited)) {
                directionIndex++
                directionIndex %= 4
            }

            // visit next element
            row += direction[directionIndex][0]
            col += direction[directionIndex][1]
        }

        return ans

    }

    fun shouldTurnDirection(nextRow: Int, nextCol: Int, rows: Int, cols: Int, visited: Array<BooleanArray>): Boolean {

        return nextRow >= rows // 超过最大行
            || nextCol >= cols // 超过最大列
            || nextRow < 0 // 0行
            || nextCol < 0 // 0列
            || visited[nextRow][nextCol] // 已经遍历过

    }

}

作者：chenguangjian2020
链接：https://leetcode-cn.com/problems/spiral-matrix/solution/luo-xuan-ju-zhen-mo-ni-fa-kotlin-by-chen-b5e8/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。