LeetCode 剑指 Offer 29. 顺时针打印矩阵
原题链接
简单
作者:
RiseAbove1
,
2023-01-09 22:15:15
,
所有人可见
,
阅读 90
class Solution {
public:
//本题与主站 54 题相同:https://leetcode-cn.com/problems/spiral-matrix/
vector<int> spiralOrder(vector<vector<int>>& matrix) {
//y总采用洪水灌溉算法(算法提高班-图论)来解决这个问题
vector<int>res;//答案
int n = matrix.size();//,m = matrix[0].size();注意不能这么写,因为如果n为0的话,访问matrix[0]就是越界!
if(!n) return res;
int m = matrix[0].size();
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};//方向偏移量(右下左上)
vector<vector<bool>> st(n,vector<bool>(m));//用来标记是否遍历过
for(int i = 0 , x = 0 ,y = 0 , d = 0; i <n*m ; i++){//一共遍历m*n次,x代表横坐标,y代表纵坐标,d表示移动的方向
res.push_back(matrix[x][y]);
st[x][y]=true;//标记为已走过
int a = x + dx[d] ,b = y + dy[d];//a和b表示在d方向上更进一步
if(a<0 || a>=n || b <0 || b >=m || st[a][b]){//如果a或b越界,则改变方向
d = (d+1)%4;//0123
a = x + dx[d] ,b = y + dy[d];
}
x = a , y = b;//经过验证可以走后,进入下一轮循环
}
return res;
}
};