第45屆國際大學生程式設計競賽 亞洲網上區域賽模擬賽 I題 Character Wheels【模擬】

傳送門：Character Wheels

題意

給你一個n*n的矩陣，保證n為偶數，從外向內總共n/2層，現在有m次操作，對于每次操作：

1. 選擇其中一層向左（逆時針）或向右（順時針）轉動y次，
2. 輸出當前的矩陣，

思路

直接模擬，

• 如果要輸出矩陣，對于每層，按矩陣的左上->右上->右下->左下的順序維護一個線性表，若需輸出新矩陣則遍歷該線性表，按其對應位置存入答案矩陣即可，
• 如果要選擇一層轉動y次，設num=y%4，若num!=0，則向右轉動num次，等效于向左轉動4-num次，然后更新每一層在對應線性表中的開始位置，

AC代碼

#include <bits/stdc++.h>
using namespace std;
const int N=52;
int n,m;
char a[N][N],ans[N][N];
int dir[4][2]={0,1,1,0,0,-1,-1,0}; // 右、下、左、上
vector<char>g[N]; // 按矩陣的左上->右上->右下->左下的順序維護一個線性表
int pos[N]; // 記錄第i層的首個字符在g[i]中的下標
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>a[i][j];
    int h=n/2; // h層
    for(int i=1;i<=h;i++)
    {
        pos[i]=0;
        int bx=i;
        int by=i;
        int k=0; // 方向
        int x=bx,y=by;
        while(1)
        {
            if(k==3&&x==bx&&y==by)break; // 向上回到起點，結束
            g[i].push_back(a[x][y]);
            int d=(h-i+1)*2-1;
            if(k==0&&x==bx&&y==by+d) // 右上角，改變方向
            	k++;
            else if(k==1&&x==bx+d&&y==by+d) // 右下角
                k++;
            else if(k==2&&x==bx+d&&y==by) // 左下角
                k++;
            x+=dir[k][0];
            y+=dir[k][1];
        }
    }
    cin>>m;
    char opt;
    while(m--)
    {
        cin>>opt;
        int k,num;
        if(opt=='P')
        {
            for(int i=1;i<=h;i++)
            {
                int bx=i,by=i;
                int x=bx,y=by;
                int cnt=pos[i];
                int k=0; // 方向
                while(1)
                {
                    if(k==3&&x==bx&&y==by)break; // 向上回到起點，結束
                    ans[x][y]=g[i][cnt];
                    cnt=(cnt+1)%g[i].size(); // 記得取模
                    int d=(h-i+1)*2-1;
                    if(k==0&&x==bx&&y==by+d) // 右上角，改變方向
                        k++;
                    else if(k==1&&x==bx+d&&y==by+d) // 右下角
                        k++;
                    else if(k==2&&x==bx+d&&y==by) // 左下角
                        k++;
                    x+=dir[k][0];
                    y+=dir[k][1];
                }
            }
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    j==n?printf("%c\n",ans[i][j]):printf("%c",ans[i][j]);
        }
        else
        {
            cin>>k>>num;
            num%=4;
            if(opt=='R'&&num!=0)num=4-num; // 轉換成L
            int d=(h-k+1)*2-1;
            pos[k]=(pos[k]+num*d)%g[k].size();
        }
    }
    return 0;
}

UPDATE 2020.11.1 簡化

其實不用按順序放到線性表里，可直接修改原矩陣，每次交換4個位置，來調整順序，

#include <bits/stdc++.h>
using namespace std;
const int N=52;
int n,m;
char s[N][N];
void rot(int k,int num) // 第k層左轉num次
{
    int h=n/2; // 共h層
    int d=(h+1-k)*2; // 第k層行(列)的長度
    while(num--)
    {
        for(int i=1;i<=d-1;i++)
        {
            int x1=k,y1=k+i-1; // 左上角往右第i個 (x1,y1)
            int x2=k+i-1,y2=k+d-1; // 右上角往下第i個 (x2,y2)
            int x3=k+d-1,y3=k+d-i; // 右下角往左第i個 (x3,y3)
            int x4=k+d-i,y4=k; // 左下角往上第i個 (x4,y4)
            swap(s[x1][y1],s[x2][y2]);
            swap(s[x2][y2],s[x3][y3]);
            swap(s[x3][y3],s[x4][y4]);
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>s[i]+1;
    cin>>m;
    while(m--)
    {
        char opt;
        cin>>opt;
        if(opt=='P')
        {
            for(int i=1;i<=n;i++)
                printf("%s\n",s[i]+1);
        }
        else
        {
            int k,num;
            cin>>k>>num;
            num%=4;
            if(opt=='R'&&num!=0)num=4-num; // 轉換成L
            rot(k,num);
        }
    }
    return 0;
}