题目描述
Scarlet最近学会了一个数组魔法,她会在n*n二维数组上将一个奇数阶方阵按照顺时针或者逆时针旋转90°,
首先,Scarlet会把1到n^2
的正整数按照从左往右,从上至下的顺序填入初始的二维数组中,然后她会施放一些简易的魔法。
Scarlet既不会什么分块特技,也不会什么Splay套Splay,她现在提供给你她的魔法执行顺序,想让你来告诉她魔法按次执行完毕后的二维数组。
输入格式
第一行两个整数n,m,表示方阵大小和魔法施放次数。
接下来mm行,每行4个整数x,y,r,z,表示在这次魔法中,Scarlet会把以第x行第y列为中心的2r+1阶矩阵按照某种时针方向旋转,其中z=0表示顺时针,z=1表示逆时针。
输出格式
输出nn行,每行nn个用空格隔开的数,表示最终所得的矩阵
我个人是用对称加折叠的方法来完成的
下图为运用动态数组初始化。
int **a;
a=new int*[n];
for(int i=0;i<n;i++){
a[i]=new int[n];
}
int t=1;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
a[i][j]=t;
t++;
}
}
顺时针旋转其实就是按照过中心点从右上到左下的线为分界线,来对称的交换,可以自己画一下图,很快就可以理解。
关键点1:就是p和q的式子,可以理解一下,问题就不大了
关键点2:做了一点点优化,就是{(i+j)>=sum}这种情况下肯定是不要了的,所以直接break就行,还节约时间。对了,如果不知道为什么要这样的话,你可以试一下不要里面的两个 if 函数,就会发现矩阵没有变,因为换过去的会被换回来
至于为什么不用swap函数,因为我发现我用swap函数会超时!!!!!!
可能对于单个的交换,这样会快一点,对于结构体可能swap会快一点。(我猜的)
逆时针我就不详细讲了,大同小异。
对折也不讲了,就是上下交换罢了。
void revolve_shun(int x,int y,int r,int**a){//顺时针
.....
for(int i=x-R;i<=x+R;i++){
for(int j=y-R;j<=y+R;j++){
if((i+j)>=sum){
break;
}
if((i+j)<sum){
p=x+(y-j);
q=y+(x-i);
b=a[p][q];
a[p][q]=a[i][j];
a[i][j]=b;
}
}
}
}
完整代码:
#include<iostream>
#include<iomanip>
#include<cstring>
#include<sstream>
#include<algorithm>
using namespace std;
void fold(int x,int y,int r,int**a){//进行对折操作
int R=r/2;
int p=0;
int b;
for(int i=x-R;i<x;i++){
for(int j=y-R;j<=y+R;j++){
p=2*x-i;
b=a[p][j];
a[p][j]=a[i][j];
a[i][j]=b;
}
}
}
void revolve_shun(int x,int y,int r,int**a){//顺时针
int sum=0;
int R=r/2;
sum=x+y;
int p,q;
int b;
for(int i=x-R;i<=x+R;i++){
for(int j=y-R;j<=y+R;j++){
if((i+j)>=sum){
break;
}
if((i+j)<sum){
p=x+(y-j);
q=y+(x-i);
b=a[p][q];
a[p][q]=a[i][j];
a[i][j]=b;
}
}
}
}
void revolve_ni(int x,int y,int r,int**a){//逆时针
int sum=0;
int R=r/2;
sum=y-x;
int p,q;
int b;
for(int i=x+R;i>=x-R;i--){
for(int j=y+R;j>=y-R;j--){
if((j-i)<=sum){
break;
}
if((j-i)>sum){
p=x-(y-j);
q=y-(x-i);
b=a[p][q];
a[p][q]=a[i][j];
a[i][j]=b;
}
}
}
}
int main(){
int n,m;
cin>>n>>m;
int **a;
a=new int*[n];
for(int i=0;i<n;i++){
a[i]=new int[n];
}
int t=1;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
a[i][j]=t;
t++;
}
}
while(m>0){
int x,y,r,z;
cin>>x>>y>>r>>z;
x--;
y--;
r=2*r+1;
if(z==0){
revolve_shun(x,y,r,a);
}else{
revolve_ni(x,y,r,a);
}
fold(x,y,r,a);
m--;
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cout<<a[i][j]<<" ";
}
cout<<endl;
}
system("pause");
return 0;
}
更多推荐
P4924 [1007]魔法少女小Scarlet(c++)
发布评论