sdut 1961dfs 귀속

1471 단어
Image Compression
픽셀은 정확도에 따라 압축하고 직접 dfs로 풀 수 있다
#include<stdio.h>
#include<string.h>
int w,t;
char map[70][70];
int f(int x,int y,int size)
{
    int i,j,sum;
    sum=0;
    for(i=x;i<x+size;i++)
    {
        for(j=y;j<y+size;j++)
            if(map[i][j]==49)
                sum++;
    }
    if(sum*100.0/(size*size)>=t*1.0)
    {
        for(i=x;i<x+size;i++)
        {
            for(j=y;j<y+size;j++)
                map[i][j]=49;
        }
        return 1;
    }
    else if(sum*100.0/(size*size)<=100.0-t)
    {
        for(i=x;i<x+size;i++)
        {
            for(j=y;j<y+size;j++)
                map[i][j]=48;
        }
        return 1;
    }
    else
        return 0;   // 
}
void dfs(int x,int y,int size)
{
    if(size==1)
        return;
    if(!f(x,y,size))
    {
        dfs(x,y,size/2);       //zuo shang
        dfs(x+size/2,y,size/2);// youshang
        dfs(x,y+size/2,size/2);//zuoxia
        dfs(x+size/2,y+size/2,size/2);//youxia
    }
}
int main()
{
    int i,j,k=1;
    while(scanf("%d",&w)&&w)
    {
        memset(map,0,sizeof(map));
        scanf("%d",&t);
        for(i=0;i<w;i++)
        {
            scanf("%s",&map[i]);
        }
        dfs(0,0,w);
        printf("Image %d:
",k++); for(i=0;i<w;i++) { puts(map[i]); } } return 0; }

좋은 웹페이지 즐겨찾기