[LeetCode 題解] Spiral Matrix

前言

【LeetCode 題解】系列傳送門：

http://www.cnblogs.com/double-win/category/573499.html

題目連結

54. Spiral Matrix

題目描述

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

For example,

Given the following matrix:

[

[ 1, 2, 3 ],

[ 4, 5, 6 ],

[ 7, 8, 9 ]

]

You should return

[1,2,3,6,9,8,7,4,5]

.

題意

按照螺旋的方式傳回矩陣中的各個元素。

例如，給定如下矩陣

其對應的結果為

[1, 2, 3, 6, 9, 8, 7, 4, 5]

思路

根據題意提取關鍵資訊：

(1) m x n elements (m rows, n columns), 沒有特意強調 m 和n 非負， 是以在邊界判斷是需要考慮空數組

(2) 螺旋的方式， 從結果可以看出是按照順時針方向依次周遊的。

每次都是按照一個方向一直周遊， 直到該方向上所有的資料都通路過， 那麼就轉換到下一個方向。

從上一個方向開始， 每個點可能的方向最多有4個， 如果四個方向的下一個點都被周遊過， 則說明碰到了終點。

解法

class Solution(object):
    def bfs(self, matrix, i, j, last = 0):
        """
        :type matrix: List[List[int]]
        :type i: int current row index
        :type j: int current column index
        :rtype: void
        """
        if self.visited[i][j] == 0:
            self.visited[i][j] = 1
            self.res.append(matrix[i][j])
        retry = 0
        while retry < 4:
            if last % 4 == 0:
                if j + 1 <= self.n - 1 and self.visited[i][j + 1] == 0:
                    self.bfs(matrix, i, j + 1, last)
            elif last % 4 == 1: 
                if i + 1 <= self.m - 1 and self.visited[i + 1][j] == 0:
                    self.bfs(matrix, i + 1, j, last)
            elif last % 4 == 2:
                if j - 1 >= 0 and self.visited[i][j - 1] == 0:
                    self.bfs(matrix, i, j - 1, last)
            elif last % 4 == 3:
                if i - 1 >= 0 and self.visited[i - 1][j] == 0:
                    self.bfs(matrix, i - 1, j, last)
            last += 1
            retry += 1


    def spiralOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        self.visited = []
        self.res = []
        self.m = len(matrix)
        if self.m == 0:
            # the matrix is empty
            return self.res
        self.n = len(matrix[0])
        for i in range(self.m):
            line = []
            for j in range(self.n):
                line.append(0)
            self.visited.append(line[:])
        self.bfs(matrix, 0, 0)
        return self.res

           

聲明

作者	Double_Win
出處	http://www.cnblogs.com/double-win/p/7979672.html

本文版權歸作者和部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連結，否則作者保留追究法律責任的權利。 若本文對你有所幫助，您的關注和推薦是我們分享知識的動力!