1105 Spiral Matrix (25分)

83 阅读 0 评论 55 点赞

我是靠谱客的博主生动黑夜，最近开发中收集的这篇文章主要介绍1105 Spiral Matrix (25分)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

同样的模拟练习：Z字形扫描

1、首先要找到m、n。要求m>=n且mn之间差距最小，然后存储vector<vector<int>> ans(m,vector<int>(n));


int m,n;//m是行数，n是列数
for(n=sqrt(num);n>=1;n--){
if(num%n==0){
m=num/n;
break;
}
}

2、用count计数来判断是否退出。用四个变量记录开始行、结束行、开始列、结束列。

#include<bits/stdc++.h>
using namespace std;
bool cmp(int a,int b){
return a>b;
}
int main(){
int num;
cin>>num;
vector<int> v(num);
for(int i=0;i<num;i++) cin>>v[i];
sort(v.begin(),v.end(),cmp);
int m,n;//m是行数，n是列数
for(n=sqrt(num);n>=1;n--){
if(num%n==0){
m=num/n;
break;
}
}
int count=0;
vector<vector<int>> ans(m,vector<int>(n));
int x1=0,x2=m-1,y1=0,y2=n-1;
while(count<num){
//→
for(int i=y1;i<=y2;i++){
ans[x1][i]=v[count++];
}
if(count>=num) break;
x1++;
//↓
for(int i=x1;i<=x2;i++){
ans[i][y2]=v[count++];
}
if(count>=num) break;
y2--;
//←
for(int i=y2;i>=y1;i--){
ans[x2][i]=v[count++];
}
if(count>=num) break;
x2--;
//↑
for(int i=x2;i>=x1;i--){
ans[i][y1]=v[count++];
}
if(count>=num) break;
y1++;
}
for(int i=0;i<m;i++){
bool flag=false;
for(int j=0;j<n;j++){
if(flag) cout<<" ";
cout<<ans[i][j];
flag=true;
}
cout<<endl;
}
return 0;
}

3、另一个做法，将问题分解为两层循环。外层循环是走圈，内层循环是左下右上动作。

需要思考：外层循环要走多少层；内层循环的起始和终止位置。

外层循环我们拿m来算，（m>n保证要走完)，每一次循环就去掉两行。那么level为m/2+m%2，

内层循环，用个图画一下，对照写。

当然可以按喜好走，以下的走法是 →一整行 ↓ 中间去两边 ←一整行 ↑ 中间去两边，这样写起来是对称的~

#include<bits/stdc++.h>
using namespace std;
bool cmp(int a,int b){
return a>b;
}
int main(){
int num;
cin>>num;
vector<int> v(num);
for(int i=0;i<num;i++) cin>>v[i];
sort(v.begin(),v.end(),cmp);
int m,n;//m是行数，n是列数
for(n=sqrt(num);n>=1;n--){
if(num%n==0){
m=num/n;
break;
}
}
int count=0;
vector<vector<int>> ans(m,vector<int>(n));
int level=m/2+m%2;
int t=0;
for(int i=0;i<level;i++){
for(int j=i;j<=n-1-i&&t<=num-1;j++)
ans[i][j]=v[t++];
for(int j=i+1;j<=m-2-i&&t<=num-1;j++)
ans[j][n-1-i]=v[t++];
for(int j=n-1-i;j>=i&&t<=num-1;j--)
ans[m-1-i][j]=v[t++];
for(int j=m-2-i;j>=i+1&&t<=num-1;j--)
ans[j][i]=v[t++];
}
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
cout<<ans[i][j];
if(j!=n-1) cout<<" ";
}
cout<<endl;
}
return 0;
}