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

SDUT - 1961: Image Compression

程序员文章站 2024-03-13 16:04:33
...

题目链接:点击打开链接

 

题目大意:给出一个 n*n 的图像和一个百分比 T,不是 0 就是 1,如果 0 占的百分比大于等于 T,则该区域全部变为 0,(1 也同理,则变为 1),确保数据 T 大于等于 51,如果都无法变,则缩小成四个象限分别重复上述操作,直到有变化为止或不能再缩为止。

 

解题思路:递归 + 四个象限的控制始末位置需要注意。

 

AC 代码

#include<bits/stdc++.h>
#include<cmath>

#define mem(a,b) memset(a,b,sizeof a);
#define INF 0x3f3f3f3f
#define MOD 1000000007

using namespace std;

typedef long long ll;

const int maxn=70;

int n, ST;
char g[maxn][maxn];

void dfs(int si,int ei,int sj,int ej,int n)
{
    if(n==0) return;

    int one=0;
    for(int i=si-1;i<ei;i++)
    {
        for(int j=sj-1;j<ej;j++)
        {
            one+=g[i][j]-'0';
        }
    }

    if(int(one*100)>=ST*n)
    {
        for(int i=si-1;i<ei;i++)
        {
            for(int j=sj-1;j<ej;j++)
            {
                g[i][j]='1';
            }
        }
        return;
    }
    if(int((n-one)*100)>=ST*n)
    {
        for(int i=si-1;i<ei;i++)
        {
            for(int j=sj-1;j<ej;j++)
            {
                g[i][j]='0';
            }
        }
        return;
    }

    dfs(si,(si+ei)/2,sj,(sj+ej)/2,n/4); // 1 象限
    dfs(si,(si+ei)/2,(sj+ej)/2+1,ej,n/4); // 2 象限
    dfs((si+ei)/2+1,ei,sj,(sj+ej)/2,n/4); // 3 象限
    dfs((si+ei)/2+1,ei,(sj+ej)/2+1,ej,n/4); // 4 象限
}

int main()
{
    int kase=1;
    while(~scanf("%d",&n) && n)
    {
        scanf("%d",&ST);
        mem(g,0);
        for(int i=0;i<n;i++)
            scanf("%s",g[i]);

        dfs(1,n,1,n,n*n);

        printf("Image %d:\n",kase++);
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
                putchar(g[i][j]);
            puts("");
        }
    }

    return 0;
}