J - Image Compression （递归模拟）

题目：file:///C:/Users/zxy/Desktop/297w

题目链接：https://cn.vjudge.net/contest/245686#problem/J

题意：将图形分为四块，每次找其中的白色块或黑色块，如果他们的占比超过t%，就将那个区域全部变成白色或者黑色；

然后再将分好的四块区域再次分成四块，依次递归下去。

心得：这道题一开始没想到用递归，后来问了大佬才知道，还要注意递归的边界。

 

#include<bits/stdc++.h>
using namespace std;
char a[120][120];
int w,t;

void df(int i1,int j1,int i2,int j2)
{
	int i,j;
	int h=0,b=0;
	double l=j2-j1+1;
	if(l<2) return ;
	for(i=i1;i<=i2;i++)
	{
		for(j=j1;j<=j2;j++)
		{
			if(a[i][j]=='1') h++;
			else if(a[i][j]=='0') b++;
		}
	}
	
	double rh=100.0*h/(h+b),rb=100.0*b/(h+b);
	if(rh>=t)
	{
		for(i=i1;i<=i2;i++)
		for(j=j1;j<=j2;j++) a[i][j]='1';
	}
	else if(rb>=t)
	{
		for(i=i1;i<=i2;i++)
		for(j=j1;j<=j2;j++) a[i][j]='0';
	}
	
	int l1=(i1+i2)/2,l2=(j1+j2)/2;
	df(i1,j1,l1,l2);
	df(i1,l2+1,l1,j2);
	df(l1+1,j1,i2,l2);
	df(l1+1,l2+1,i2,j2);
}

int main(void)
{
	int i,j,pt=1;
	while(~scanf("%d",&w))
	{
		if(w==0) break;
		memset(a,0,sizeof(a));
		scanf("%d",&t);
		for(i=0;i<w;i++) scanf("%s",a[i]);
		
		df(0,0,w-1,w-1);
		printf("Image %d:\n",pt++);
		for(i=0;i<w;i++)
		{
			for(j=0;j<w;j++)
			printf("%c",a[i][j]);
			printf("\n");
		}
	}
	
	return 0;
}