一：Spiral Matrix I
题目：
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].
链接：https://leetcode.com/problems/spiral-matrix/
分析：看代码，四个while循环形成一个大圈
?
class Solution {
public:
void dfs(int xi, int yi, const int &m, const int &n, vector
> &matrix, vector
&result, int **visited){ visited[xi][yi] = 1; result.push_back(matrix[xi][yi]); while(yi+1 < n && !visited[xi][yi+1]){ // 四个while循环刚好跑了大正圈 result.push_back(matrix[xi][yi+1]); visited[xi][yi+1] = 1; yi = yi+1; } while(xi+1 < m && !visited[xi+1][yi]){ result.push_back(matrix[xi+1][yi]); visited[xi+1][yi] = 1; xi = xi +1; } while(yi-1 >=0 && !visited[xi][yi-1]){ result.push_back(matrix[xi][yi-1]); visited[xi][yi-1] = 1; yi = yi-1; } while(xi-1 >=0 && !visited[xi-1][yi]){ result.push_back(matrix[xi-1][yi]); visited[xi-1][yi] = 1; xi = xi-1; } if(yi+1 < n && !visited[xi][yi+1]) dfs(xi, yi+1, m, n, matrix, result, visited); } vector
spiralOrder(vector
> &matrix) { vector
result; int m = matrix.size(); if(m == 0) return result; int n = matrix[0].size(); int **visited= new int*[m]; for(int i = 0; i < m; i++){ visited[i] = new int[n]; memset(visited[i], 0, sizeof(int)*n); } dfs(0, 0, m, n, matrix, result, visited); for(int i = 0; i < m; i++) delete [] visited[i]; delete []visited; return result; } };
二：Spiral Matrix II
?
题目：
?
Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.
For example,
Given n = 3,
You should return the following matrix:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]
?
?
class Solution {
public:
void dfs(int xi, int yi, const int &n, vector
> &result, int &value){
result[xi][yi] = value++;
while(yi+1 < n && !result[xi][yi+1]){ // 四个while循环刚好跑了大正圈
result[xi][yi+1] = value++;
yi = yi+1;
}
while(xi+1 < n && !result[xi+1][yi]){
result[xi+1][yi] = value++;
xi = xi+1;
}
while(yi-1 >= 0 && !result[xi][yi-1]){
result[xi][yi-1] = value++;
yi = yi-1;
}
while(xi-1 >= 0 && !result[xi-1][yi]){
result[xi-1][yi] = value++;
xi = xi-1;
}
if(yi+1 < n && !result[xi][yi+1]) dfs(xi, yi+1, n, result, value);
}
vector
> generateMatrix(int n) { vector
>result; if(n == 0) return result; for(int i = 0; i < n; i++){ // 初始化result vector
temp(n, 0); result.push_back(temp); } int value = 1; dfs(0,0, n, result, value); return result; } };
?