2023“钉耙编程”中国大学生算法设计超级联赛（3）8-bit Zoom

2023“钉耙编程”中国大学生算法设计超级联赛（3）8-bit Zoom

题解

有一张尺寸为$n\times n$的图片，你要将图片放大成大小为$\frac{nZ}{100}\times \frac{nZ}{100}$的图片。

当下列任何一个条件不成立时，图片不能放大成上述的图片：

• $\frac{nZ}{100}$不是整数
• 在放大的图片中，无法确定某些像素的颜色

给出图片，求能否放大成上述的图片。如果可以的话，输出放大后的图片；否则，输出$\text{error}$。

有$T$组数据。

$1\le T\le 10,1\le n\le 50,100\le Z\le 200,Z\%25=0$

题解

先判断$\frac{nZ}{100}$是不是整数，不是的话输出$\text{error}$。

先将图放大$\frac{Z}{25}$倍，这样的话，原图的每个$1\times 1$的格子在放大后的图中变为$\frac{Z}{25}\times \frac{Z}{25}$的格子。

然后，将图片缩到原来的$\frac{1}{4}$，将每个$4\times 4$的部分变为一个格子。如果出现一个$4\times 4$的部分存在两个像素的颜色不相同的情况，则不合法，输出$\text{error}$。

放大$\frac{Z}{25}$倍后再缩到原来的$\frac{1}{4}$，也就是将原图放大$\frac{Z}{100}$倍，符合题意。如果经过放大在缩小后的图合法，则将最后的图输出即可。

时间复杂度为$O(n^2)$。

code

#include<bits/stdc++.h>
using namespace std;
int t,n,Z,w,fl;
char a[105][105],b[505][505];
char gt(){char ch=getchar();while(ch<'a'||ch>'z') ch=getchar();return ch;
}
int main()
{scanf("%d",&t);while(t--){scanf("%d%d",&n,&Z);for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){a[i][j]=gt();}}if(n*Z%100!=0){printf("error\n");continue;}w=Z/25;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){for(int k=(i-1)*w+1;k<=i*w;k++){for(int l=(j-1)*w+1;l<=j*w;l++){b[k][l]=a[i][j];}}}}fl=0;for(int i=1;i<=n*w;i+=4){for(int j=1;j<=n*w;j+=4){for(int k=0;k<4;k++){for(int l=0;l<4;l++){if(b[i+k][j+l]!=b[i][j]) fl=1;}}}}if(fl) printf("error\n");else{for(int i=1;i<=n*w;i+=4){for(int j=1;j<=n*w;j+=4){printf("%c",b[i][j]);}printf("\n");}}}return 0;
}