93全國資訊學科能力決賽 3. 黑白影像的四分樹表示法
作法 : 遞迴解 (DFS)
題目非常的難懂 (TO ME) ,在此感謝阿尼雅的講解
可是我也不太會說明 /*你可以看遞迴的部份 了解題目的意思@@(應該)*/
/***********************************************************/
#include<stdio.h>
#include<stdlib.h>
int s2[11]={1,2,4,8,16,32,64,128,256,512,1024};
char map[256][256]={0};
int check(int x,int y,int L)
{
int a,b,time[3]={0};
for(a=x;a<x+L;a++)
for(b=y;b<y+L;b++)
if(map[a][b]==1) time[1]=1; /*黑色*/
else time[2]=1; /*白色*/
if(time[1]==1&&time[2]==1) return 3;/*printf("g ");*/
else if(time[1]==1&&time[2]==0) return 2;/*printf("b ");*/
else return 1;/*printf("w ");*/
}
void DFS(int x,int y,int L)
{
int t=check(x-s2[L+1]+1,y,s2[L+1]);
if(t==3) printf("g ");
else if(t==2) {printf("b ");return;}
else {printf("w ");return;}
DFS(x-s2[L],y+s2[L],L-1);
DFS(x-s2[L],y ,L-1);
DFS(x ,y ,L-1);
DFS(x ,y+s2[L],L-1);
}
main()
{
int N;
while(scanf("%d",&N)==1)
{
int a,b,c;
for(a=0;a<N;a++)
{
scanf("%s",map[a]);
for(b=0;b<N;b++)
map[a][b]-=48;
}
for(a=0;a<11;a++)
if(s2[a]==N) break;
DFS(N-1,0,a-1);
printf("\n");
}
return 0;
}