代码借鉴：http://www.cnblogs.com/npugen/p/9527453.html
1 #include <bits/stdc++.h> 2 #define _for(i,a,b) for(int i = (a);i < (b);i ++) 3 using namespace std; 4 //1 2 5 //3 4 6 7 const int maxn = 70; 8 int n,cnt; 9 char gra[maxn][maxn]; 10 vector<int> ans; 11 vector<int> num; 12 13 bool is_black(int r,int c,int wide) 14 { 15 _for(i,r,r+wide) 16 _for(j,c,c+wide) 17 if(gra[i][j] == '0') return false; 18 return true; 19 } 20 21 bool is_white(int r,int c,int wide) 22 { 23 _for(i,r,r+wide) 24 _for(j,c,c+wide) 25 if(gra[i][j] == '1') return false; 26 return true; 27 } 28 29 int consumption(string &ss) 30 { 31 int res = 0; 32 for(int i = ss.size()-1;i >= 0;i --) 33 { 34 res *= 5; 35 res += ss[i]-'0'; 36 } 37 return res; 38 } 39 40 void cal(string str,int r,int c,int wide) 41 { 42 if(is_black(r,c,wide)) 43 { 44 ans.push_back(consumption(str)); 45 } 46 else if(is_white(r,c,wide)) 47 ; 48 else 49 { 50 cal(str+"1",r,c,wide/2); 51 cal(str+"2",r,c+wide/2,wide/2); 52 cal(str+"3",r+wide/2,c,wide/2); 53 cal(str+"4",r+wide/2,c+wide/2,wide/2); 54 } 55 } 56 57 int solve(int n) 58 { 59 cnt = 0; 60 ans.clear(); 61 memset(gra,0,sizeof(gra)); 62 _for(i,0,n) scanf("%s",gra[i]); 63 string str = ""; 64 if(is_black(0,0,n)) return 1; 65 if(is_white(0,0,n)) return -1; 66 cal(str+"1",0,0,n/2); 67 cal(str+"2",0,n/2,n/2); 68 cal(str+"3",n/2,0,n/2); 69 cal(str+"4",n/2,n/2,n/2); 70 return 0; 71 } 72 73 void converse(int val,string &ss) 74 { 75 while(val) 76 { 77 ss += (val%5+'0'); 78 val /= 5; 79 } 80 } 81 82 void draw(string &ss,int pos,int r,int c,int wide) 83 { 84 if(pos == ss.size()) 85 { 86 _for(i,r,r+wide) 87 _for(j,c,c+wide) 88 gra[i][j] = '*'; 89 return ; 90 } 91 if(ss[pos] == '1') 92 draw(ss,pos+1,r,c,wide/2); 93 else if(ss[pos] == '2') 94 draw(ss,pos+1,r,c+wide/2,wide/2); 95 else if(ss[pos] == '3') 96 draw(ss,pos+1,r+wide/2,c,wide/2); 97 else if(ss[pos] == '4') 98 draw(ss,pos+1,r+wide/2,c+wide/2,wide/2); 99 } 100 101 void solve2(int n) 102 { 103 int x; 104 num.clear(); 105 memset(gra,0,sizeof(gra)); 106 while(scanf("%d",&x) && x!=-1) num.push_back(x); 107 if(num.size()==1 && num[0]==0) 108 { 109 _for(i,0,n) 110 { 111 _for(j,0,n) 112 { 113 cout << "*"; 114 } 115 cout << endl; 116 } 117 return ; 118 } 119 _for(i,0,num.size()) 120 { 121 string ss = ""; 122 converse(num[i],ss); 123 draw(ss,0,0,0,n); 124 } 125 126 _for(i,0,n) 127 { 128 _for(j,0,n) 129 { 130 if(gra[i][j]== '*') cout << gra[i][j]; 131 else cout << "."; 132 } 133 cout << endl; 134 } 135 } 136 137 int iCase = 1; 138 139 int main() 140 { 141 bool flag = false; 142 while(~scanf("%d",&n) && n) 143 { 144 if(flag) cout << endl; 145 flag = true; 146 if(n > 0) 147 { 148 int flag = solve(n); 149 printf("Image %d ",iCase ++); 150 if(flag == 1) 151 { 152 printf("%d ",0); 153 printf("Total number of black nodes = %d ",1); 154 } 155 else if(flag == -1) 156 { 157 printf("Total number of black nodes = %d ",0); 158 } 159 else 160 { 161 sort(ans.begin(),ans.end()); 162 int cnt = 0; 163 _for(i,0,ans.size()) 164 { 165 if(cnt == 0) printf("%d",ans[i]); 166 else printf(" %d",ans[i]); 167 cnt ++; 168 if(cnt == 12) cnt = 0,printf(" "); 169 } 170 if(ans.size()%12) printf(" "); 171 printf("Total number of black nodes = %d ",ans.size()); 172 } 173 } 174 else 175 { 176 printf("Image %d ",iCase ++); 177 solve2(-n); 178 } 179 } 180 return 0; 181 }