P4924 [1007]魔法少女小Scarlet（c++）

題目描述

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;
}