input
8 00000000 00000000 00001111 00001111 00011111 00111111 00111100 00111000 -8 9 14 17 22 23 44 63 69 88 94 113 -1 2 00 00 -4 0 -1 0
output
Image 1 9 14 17 22 23 44 63 69 88 94 113 Total number of black nodes = 11 Image 2 ........ ........ ....**** ....**** ...***** ..****** ..****.. ..***... Image 3 Total number of black nodes = 0 Image 4 **** **** **** ****
这题目就是给你黑白点图的两种表示方法让你互相转化，写的时候没注意格式。
数字是代表四分树黑色结点到根的距离，由于定义是递归的，所以不必真的把树建出来。
/* Created by Rey Chen on 2015.6.30 Copyright (c) 2015 Rey . All rights reserved. */ #include<cstdio> #include<algorithm> using namespace std; const int maxn = 65; char G[maxn][maxn]; int path[maxn*maxn]; int sz; void solve1(int r1,int c1,int r2,int c2,int wei,int sum) { bool whi, bla; whi = bla = false; for(int i = r1;i <= r2;i++) for(int j = c1;j <= c2;j++){ if(!bla && G[i][j] == '1') bla = true; if(!whi && G[i][j] == '0') whi = true; if(whi&&bla) { break;} } if(bla) { if(!whi) {path[++sz] = sum; return;} }else if(whi) return; int dvr = r1+r2>>1, dvc = c1+c2>>1; int nwei = 5*wei; solve1( r1, c1,dvr,dvc,nwei,sum+ wei ); solve1( r1,dvc+1,dvr, c2,nwei,sum+(wei<<1)); solve1(dvr+1, c1 ,r2,dvc,nwei,sum+ wei*3 ); solve1(dvr+1,dvc+1, r2 ,c2,nwei,sum+(wei<<2)); } int a[20]; void draw(int n,int r1,int c1,int r2,int c2){ int Sz = 0; while(n){ a[Sz++]=n%5;n/=5;} for(int i = 0; i < Sz;i++){ switch (a[i]){ case 1:{ r2 = r1+r2>>1; c2 = c1+c2>>1; break; } case 2:{ r2 = r1+r2>>1; c1 = (c1+c2>>1)+1; break; } case 3:{ r1 = (r1+r2>>1)+1; c2 = c1+c2>>1; break; } case 4:{ r1 = (r1+r2>>1)+1; c1 = (c1+c2>>1)+1; break; } } } for(int i = r1;i <= r2;i++) for(int j = c1;j <= c2;j++) G[i][j] = '*'; } int main() { int n; int Cas = 0; while(~scanf("%d",&n)&&n){ if(Cas) puts(""); if(n>0){ for(int i = 0; i < n; i++) scanf("%s",G[i]); sz = 0; solve1(0,0,n-1,n-1,1,0); sort(path+1,path+sz+1); printf("Image %d ",++Cas); for(int i = 1; i < sz; i++)//PE了。。。 printf("%d%c",path[i],i%12?' ':' '); if(sz)printf("%d ",path[sz]); printf("Total number of black nodes = %d ",sz); }else { n = -n; int t; for(int i = 0;i < n;i++){ for(int j = 0;j < n;j++) G[i][j]='.'; G[i][n] = ' '; } while(scanf("%d",&t)&&~t){ draw(t,0,0,n-1,n-1); } printf("Image %d ",++Cas); for(int i = 0;i < n;i++) puts(G[i]); } } return 0; }