当前位置：首页 > news >正文

2023-08-07力扣今日二题

news 2025/8/27 12:48:48

链接：

剑指 Offer 29. 顺时针打印矩阵

题意：

如题

解：

麻烦的简单题，具体操作类似走地图，使用一个长度四的数组表示移动方向

我这边的思路是如果按正常的方向没有路走了，那转向下一个方向一定有路，不然就是最后一格了

所以每次就先找下一个位置，然后check函数判断是否合法（走过的设置为INT_MAX），合法的话输出自身然后移动到下一个位置，不合法的话就转向判断下一个位置是否合法，这时候如果转完还不合法，则退出

退出的时候最后一格还没有输出，所以输出一下

PS：之前我是用-1当标记的，结果卡了一组数据，换了INT_MAX然后AC了，不过出题没给范围，应该是包含整数范围的，也算是偷鸡了，不过用longlong配LLONG_MAX也是一样的，所以无所谓啦

实际代码：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
PII add(const PII& lhs,const PII& rhs)
{PII ret{0,0};ret.first=lhs.first+rhs.first;ret.second=lhs.second+rhs.second;return ret;
}
bool check(const PII& now,const int& lgr,const int& lgc,const vector<vector<int>>& matrixCopy)
{if(now.first<0||now.first>=lgr) return false;if(now.second<0||now.second>=lgc) return false;if(matrixCopy[now.first][now.second]==INT_MAX) return false;return true;
}
vector<int> spiralOrder(vector<vector<int>>& matrix)
{vector<int> ret;//答案 vector<vector<int>>matrixCopy(matrix);//拷贝原数组 int zt=0,moved=0;PII move[4]={ {0,1},{1,0},{0,-1},{-1,0}};//移动相关 int lgrow=matrix.size();if(!lgrow) return ret;//行数 int lgcol=matrix[0].size();if(!lgcol) return ret;//列数 PII start={0,0};//起点while(true){PII next=add(start,move[zt]);//cout<<"next:"<<next.first<<" "<<next.second<<endl;if(check(next,lgrow,lgcol,matrixCopy))//有路 {ret.push_back(matrixCopy[start.first][start.second]);matrixCopy[start.first][start.second]=INT_MAX;start=next;moved++;}else//没路 {zt++;zt%=4;moved=0;//转向 next=add(start,move[zt]);if(check(next,lgrow,lgcol,matrixCopy)) continue;//转完以后有没有路 else break;}}ret.push_back(matrixCopy[start.first][start.second]);return ret;
}
int main()
{vector<vector<int>> matrix;int n,m,temp;cin>>n>>m;for(int i=0;i<n;i++){vector<int>t;for(int j=0;j<m;j++){cin>>temp;t.push_back(temp);}matrix.push_back(t);}vector<int>ans=spiralOrder(matrix);for(auto &a:ans) cout<<a<<ends;return 0;
}

限制：