原题:
输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。
样例
输入:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
输出:[1,2,3,4,8,12,11,10,9,5,6,7
分析:
题目中说要顺时针打印矩阵,所以遍历矩阵的顺序为:右->下->左->上。
什么时候换方向呢? 当走到了边界,或者沿着当前方向继续走下一个数已经遍历过了的时候需要改变方向。
代码:
class Solution {
public:
vector<int> printMatrix(vector<vector<int>>& matrix) {
//思想:按照四个方向走,四个方向的顺序为右->下->左->上
// 当一个方向走不下去了在走另一个方向。
vector<int> res;
//如果为矩阵为空,直接返回
if(matrix.size() == 0) return res;
//矩阵的下边界
int down = matrix.size();
//矩阵的右边界
int right = matrix[0].size();
//遍历矩阵的四个方向:dx为行的方向,dy为列的方向
vector<int> dx={-1,0,1,0};
vector<int> dy={0,1,0,-1};
//d表示当前的方向,最开始从往右走开始,对应dx[1]=0,dy[1]=1;
int d = 1;
//当前的坐标:x,y
int x=0,y=0;
//标记当前位置是否遍历过
vector<vector<bool>>flag (down, vector<bool>(right,false));
for(int i = 0;i < down * right;i ++){
// 遍历过的位置flag标记为true
flag[x][y] = true;
res.push_back(matrix[x][y]);
//a和b表示下一个遍历的位置
int a = x + dx[d];
int b = y + dy[d];
// 如果当前方向遍历完了,需要改变方向
if(a < 0 || a >= down || b < 0 || b >= right || flag[a][b]){
d = (d + 1) % 4;
a = x + dx[d];
b = y + dy[d];
}
x = a;
y = b;
}
return res;
}
};