题解 [ABC375C] Spiral Rotation

cjh20090318 · 2024-10-15 11:22:25 · 题解

近 40 场以来最难的 C，有点难写。

题意

有一个 N \times N 的网格，每个网格由黑色 # 和白色 . 组成。

按照顺序 i = 1, 2, \ldots, \frac{N}{2} 依次以下进行操作：

• 对于 i 和 N + 1 - i 之间的所有整数对 x, y ，用单元格 (x, y) 的颜色替换单元格 (y, N + 1 - x) 的颜色。同时对所有这些单元格对 x, y 进行替换。

最后找出每个单元格的颜色。

分析

这个操作感觉没有说人话，经过一定的模拟发现，每一次操作即把一个左上顶点为 (i,i)，右下顶点为 (N-i+1,N-i+1) 的正方形顺时针旋转 90 度。

直接暴力的对于每个 i 旋转是不可取的，需要考虑更好的方法。

设第 i 层表示的单元格集合为 \{ (x,y) \mid x = i \lor x = N-i+1 \lor y = i \lor y = N-i+1\}。

因为外层的影响，第 i 层将会被旋转 i 次，但是因为 4 次就会被转回原位，所以就只需要转 i \bmod 4 次即可。

时间复杂度 O(n^2)，具体实现有点复杂所以请看代码。

代码

//the code is from chenjh
#include<cstdio>
using namespace std;
int n;
char s[3005][3005],b[3005][3005];
void r(const int i){
    //对第 i 层进行右旋。
    for(int j=i;j<=n-i;j++) b[j][n-i+1]=s[i][j];
    for(int j=i;j<=n-i;j++) b[n-i+1][n-j+1]=s[j][n-i+1];
    for(int j=n-i+1;j>i;j--) b[j][i]=s[n-i+1][j];
    for(int j=n-i+1;j>i;j--) b[i][n-j+1]=s[j][i];
    //将临时存储的数组复制回原数组。
    for(int j=i;j<=n-i;j++) s[i][j]=b[i][j];
    for(int j=i;j<=n-i;j++) s[j][n-i+1]=b[j][n-i+1];
    for(int j=n-i+1;j>i;j--) s[n-i+1][j]=b[n-i+1][j];
    for(int j=n-i+1;j>i;j--) s[j][i]=b[j][i];
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
    for(int i=1;i<=(n>>1);i++)for(int _=i&3;_--;)r(i);//i&3 和 i%4 等价。
    for(int i=1;i<=n;i++) puts(s[i]+1);
    return 0;
}