欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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]);
    }
}