样例&&题目大意

这是codevita上的一道题,找不到原题题面了,只能凭记忆复述一遍...

输入样例1
5
O I M U R
J V U X A
X W T S R
K Z F H D
Q W K V M
输出样例1
-2 2
X J O I M
K X S H U
Q U T F R
W V W Z A
K V M D R
在这里插入图片描述

输入样例2
7
A C D S X W S
S D X W S A Z
W S D F E B A
S W S L D C D
S I X K S I D
S K D J S O D
W I D K C M C
输出样例2
4 1 -2
X W S Z A D D
S X W S A B D
D D X S D C C
C S K L F I M
A W S D E O C
S I K D J S K
W S S S W I D
在这里插入图片描述

题目意思是给你一个nn的矩阵,保证n为奇数且n<=1000,矩阵从外到内有很多层(不把矩阵最中心的那个单独的点算做一层,显然n*n的矩阵有 (int)(n/2) 层),我们假设最外层是第1层,往内一层是第2层,依次类推。比如说第1层是(1,1)->(1,n)->(n,n)->(n,1)->(1,1),第2层是(2,2)->(2,n-1)->(n-1,n-1)->(n-1,2)->(2,2)。现在你可以旋转矩阵的每一层,可以顺时针也可以逆时针,最终使得每一层的字母X都转到这一层的左上角*(保证每一层都只有一个X),比如说第一层左上角就是(1,1),第二层左上角就是(2,2)。

你需要输出:
第1行:从外到内的每一层最少需要旋转的次数,输出 (int)(n/2) 个数,以空格隔开。如果是逆时针旋转输出正数,顺时针旋转输出负数。
第2~n+1行:最终旋转后的矩阵。

思路

直接模拟,这好像也没什么算法。

~~这种模拟题,就是容易想,不好写,代码量可能巨长,队友现场写了几个小时,将近200行代码,AC的那一刻激动到热泪...~~

具体做法就是把每一层都按 左上角->右上角->右下角->左下角->左上角 的顺序遍历,存到队列里,然后把队列中字母X之前的元素依次移到队尾,使字母X为队首元素,然后把队列中的元素再按 左上角->右上角->右下角->左下角->左上角 的顺序赋值给矩阵,也就是旋转后的矩阵。

AC代码(赛后整理)

#include <bits/stdc++.h>
using namespace std;
const int N=1010;
char tmp,a[N][N],b[N][N];
int n,cnt,ans[N];
int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
queue<char>q;
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 bx1=0,by1=0;
    int bx2=0,by2=n+1;
    int bx3=n+1,by3=n+1;
    int bx4=n+1,by4=0;
    for(int k=1;k<=n/2;k++)//第k层
    {
        bx1++;by1++;//(bx1,by1)为第k层左上角坐标
        bx2++;by2--;//(bx2,by2)为第k层右上角坐标
        bx3--;by3--;//(bx3,by3)为第k层右下角坐标
        bx4--;by4++;//(bx4,by4)为第k层左下角坐标
        int nx=bx1,ny=by1;//起点为左上角(bx1,by1),向右走
        int i=0;//i为当前走的方向,i=0向右走,i=1向下走,i=2向左走,i=3向上走
        q.push(a[bx1][by1]);
        while(1)//把第k层所有元素按顺序放入队列中
        {
            nx+=dir[i][0];
            ny+=dir[i][1];
            if(i==0)
            {
                q.push(a[nx][ny]);
                if(nx==bx2&&ny==by2)i++;//向右走到了右上角,改变方向为下
            }
            else if(i==1)
            {
                q.push(a[nx][ny]);
                if(nx==bx3&&ny==by3)i++;//向下走到了右下角,改变方向为左
            }
            else if(i==2)
            {
                q.push(a[nx][ny]);
                if(nx==bx4&&ny==by4)i++;//向左走到了左下角,改变方向为上
            }
            else if(i==3)
            {
                if(nx==bx1&&ny==by1)break;//向上走,回到了左上角,第k层遍历结束
                q.push(a[nx][ny]);
            }
        }
        int s1=0;
        while(1)//把队列中字母X之前的所有元素都移到X之后,保证X是队列的第一个元素
        {
            tmp=q.front();
            if(tmp=='X')break;
            s1++;
            q.pop();
            q.push(tmp);
        }
        int s2=q.size()-s1;
        ans[k]=min(s1,s2);//s1为把X旋转到左上角所需的逆时针旋转次数,s2为所需的顺时针旋转次数
        if(s2<=s1)ans[k]=(-ans[k]);//取顺时针旋转次数少,答案为负值
        nx=bx1,ny=by1;//重置起点
        i=0;//重置方向
        while(!q.empty())//把队列中所有元素按顺序放入数组b中,数组b保存旋转后的矩阵
        {
            tmp=q.front();q.pop();
            b[nx][ny]=tmp;
            nx+=dir[i][0];
            ny+=dir[i][1];
            if(i==0&&nx==bx2&&ny==by2)i++;
            else if(i==1&&nx==bx3&&ny==by3)i++;
            else if(i==2&&nx==bx4&&ny==by4)i++;
        }
    }
    b[n/2+1][n/2+1]=a[n/2+1][n/2+1];//把最中心的那个点(n/2+1,n/2+1)的字符直接赋值给b
    for(int i=1;i<=n/2;i++)
        i==n/2?printf("%d\n",ans[i]):printf("%d ",ans[i]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        j==n?printf("%c\n",b[i][j]):printf("%c ",b[i][j]);
    return 0;
}

队友wyz的代码:

#include <bits/stdc++.h>
using namespace std;
char a[1002][1002],b[4005][1002],ans[4005][1002];
int n,cnt,X[4005],coun[4005];
int judge(int x,int y)//判断是第几层
{
    int ans=min(x,y);
    ans=min(min(n-x-1,n-y-1),ans);
    return ans;//第ans层
}
void init()
{
      for(int i=0;i<n;i++)
         for(int j=0;j<n;j++)
         {
             int t=judge(i,j);
             if(a[i][j]=='X')
             {
                if(j>=i)X[t]=i+j-2*t;
                else X[t]=-(i+j-2*t);
             }
         }
    for(int i=0;i<n/2;i++)
    {
        int x,y;x=i,y=i; cnt=0;
        for(int j=0;j<4;j++)
        {
            if(j==0)
            {
                while(y<n-i)
                {
                    b[i][cnt++]=a[x][y];
                    y++;
                }
                y--;
            }
            else if(j==1)
            {
                x++;
                while(x<n-i)
                {
                    b[i][cnt++]=a[x][y];
                    x++;
                }
                x--;
            }
            else if(j==2)
            {
                y--;
                while(y>=i)
                {
                    b[i][cnt++]=a[x][y];
                    y--;
                }
                y++;
            }
            else
            {
                x--;
                while(x>i)
                {
                    b[i][cnt++]=a[x][y];
                    x--;
                }
                x++;
            }
        }
    }
}
void out_put()
{
    for(int i=0;i<n/2;i++)
    {
        int x,y;x=i,y=i; cnt=0;
        for(int j=0;j<4;j++)
        {
            if(j==0)
            {
                while(y<n-i)
                {
                    a[x][y]=ans[i][coun[i]++];
                    y++;
                }
                y--;
            }
            else if(j==1)
            {
                x++;
                while(x<n-i)
                {
                    a[x][y]=ans[i][coun[i]++];
                    x++;
                }
                x--;
            }
            else if(j==2)
            {
                y--;
                while(y>=i)
                {
                    a[x][y]=ans[i][coun[i]++];
                    y--;
                }
                y++;
            }
            else
            {
                x--;
                while(x>i)
                {
                    a[x][y]=ans[i][coun[i]++];
                    x--;
                }
                x++;
            }
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n-1;j++)
            cout<<a[i][j]<<' ';
        cout<<a[i][n-1]<<endl;
    }
}
int main()
{
     cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        cin>>a[i][j];
    init();
    for(int i=0;i<n/2-1;i++)
        cout<<X[i]<<' ';
    cout<<X[n/2-1]<<endl;
    for(int i=0;i<n/2;i++)
    {
        int len=4*(n-2*i-1),t=-X[i];
        for(int j=0;j<len;j++)
            ans[i][(j+t+len)%len]=b[i][j];
    }
    out_put();
    return 0;
}