SDUT - 1961: Image Compression

题目链接：点击打开链接

 

题目大意：给出一个 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;
}