题目描述
输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。
样例
输入:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
输出:[1,2,3,4,8,12,11,10,9,5,6,7]
递归算法
递归按顺时针访问矩阵的元素并保存在结果中。
时间复杂度O(mn)
C++ 代码
class Solution {
public:
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
void visit(vector<int>& res, vector<vector<bool>>& st, vector<vector<int>>& matrix, int x, int y, int d){
res.push_back(matrix[x][y]);
st[x][y] = true;
int cnt = 0;
for(int i = d; cnt < 4; i = (i + 1)%4){ // 将过来的方向作为本次的起始方向
int xx = x + dx[i], yy = y + dy[i];
if(xx >= 0 && xx < matrix.size() && yy >= 0 && yy < matrix[0].size() && !st[xx][yy]){
visit(res, st, matrix, xx, yy, i);
}
cnt ++;
}
return;
}
vector<int> printMatrix(vector<vector<int> > matrix) {
if(!matrix.size() || !matrix[0].size()) return {};
vector<int> res;
vector<vector<bool>> st(matrix.size(), (vector<bool>(matrix[0].size())));
visit(res, st, matrix, 0, 0, 0);
return res;
}
};