problem:
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]
.
Hide Tags Array 題意:順時針螺旋輸出矩陣
thinking:
(1)首先想到方法是DFS,把外圈的數字輸出之後,矩陣的行和列都縮減了2,遞歸調用。思路簡單。
(2)全局搜索,考慮用DFS。與方法一類似,只是DFS思路略有不同,這裡參考:http://www.cnblogs.com/remlostime/archive/2012/11/18/2775708.html
一直關注他的實現,簡潔高效,膜拜中
開一個數組用來保存,之前這個單元是否被使用過,並配合邊界判斷,DFS,最後得出結果。空間復雜度O(n*m),時間O(n*m)
code:
class Solution { private: int step[4][2]; vectorret; bool canUse[100][100]; public: void dfs(vector > &matrix, int direct, int x, int y) { for(int i = 0; i < 4; i++) { int j = (direct + i) % 4; int tx = x + step[j][0]; int ty = y + step[j][1]; if (0 <= tx && tx < matrix.size() && 0 <= ty && ty < matrix[0].size() && canUse[tx][ty]) { canUse[tx][ty] = false; ret.push_back(matrix[tx][ty]); dfs(matrix, j, tx, ty); } } } vector spiralOrder(vector > &matrix) { // Start typing your C/C++ solution below // DO NOT write int main() function step[0][0] = 0; step[0][1] = 1; step[1][0] = 1; step[1][1] = 0; step[2][0] = 0; step[2][1] = -1; step[3][0] = -1; step[3][1] = 0; ret.clear(); memset(canUse, true, sizeof(canUse)); dfs(matrix, 0, 0, -1); return ret; } };