UVA 4926 Image Compression(递归)
程序员文章站
2024-03-13 15:34:03
...
【题目】
传送门:UVALive - 4926 Image Compression
【题解】
这题目可把我看的恶心坏了!所以说下次就不要看无用的题干直奔主题吧!
题意:给定图的大小n*n,给定占比m,若图中1或者0的占比超过m,则全部变为占比多的数字,否则将图分为四块一模一样的子图继续判断,最后输出变换后的图。
思路:递归。
【代码】
#include<stdio.h>
#include<string.h>
char mp[70][70];
int n,m;
void dfs(int x,int y,int xx,int yy)
{
int sum=0,i,j;
for(i=x;i<=xx;i++)
for(j=y;j<=yy;j++)
{
if(mp[i][j]=='1')
sum++;
}
int c=(xx-x+1)*(yy-y+1);
if(sum*100.0/c>=m)
{
for(i=x;i<=xx;i++)
for(j=y;j<=yy;j++)
mp[i][j]='1';
return;
}
else if((c-sum)*100.0/c>=m)
{
for(i=x;i<=xx;i++)
for(j=y;j<=yy;j++)
mp[i][j]='0';
return;
}
else
{
dfs(x,y,(x+xx)/2,(y+yy)/2);
dfs((x+xx)/2+1,(y+yy)/2+1,xx,yy);
dfs(x,(y+yy)/2+1,(x+xx)/2,yy);
dfs((x+xx)/2+1,y,xx,(y+yy)/2);
}
}
main()
{
int t=0;
while(~scanf("%d",&n),n)
{
int i,j;
scanf("%d",&m);
for(i=0;i<n;i++)
scanf("%s",mp[i]);
dfs(0,0,n-1,n-1);
printf("Image %d:\n",++t);
for(i=0;i<n;i++)
printf("%s\n",mp[i]);
}
}