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