题意：输入一个整数1 <= k <= 100,为测试组数，接着每组测试数据先输入一个整数N，N <= 512且N是2的次幂，然后输入一个N*N的矩阵，矩阵元素的值为0或为1，如果整个N*N的矩阵是全0（或者全1），则记录为00（或者01），不用继续拆分；否则，记录为1，并将矩阵一分为四，西北、东北、西南、东南各一块，并按此顺序审查各分块是否都是全0或者全1， 不是的话继续四分，最后把所有的01串连起来，转换为十六进制输出即可。
题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1788
——>>利用读入的数据递归建立4分树（注意边界条件：当矩阵只有1个元素即拆分到了1*1的矩阵时，肯定为0或者1，这时就是一个递归边界。），再对4分树进行层次遍历，最后转换成16进制数输出。
#include <iostream>
#include <string.h>
#include <queue>using namespace std;const int maxn = 512 + 10;typedef struct Tquadtree //定义4分树的结点数据类型
{char val[3]; //val用来标明是00、01、1的状态struct Tquadtree *q[4]; //4分树的4个叉
}quadtree;char MAP[maxn][maxn]; //输入的图quadtree* dfs(int r, int c, int s) //深度由下往上合并建树，r为行坐标，c为纵坐标，s为长度
{int i;quadtree *temp = new quadtree;if(s == 1) //当长度已为单位长度时，标记值即为该点的值，返回{temp->val[0] = '0';temp->val[1] = MAP[r][c];temp->val[2] = 0; //这是空！！！return temp;}s = s/2; //将长度二分temp->q[0] = dfs(r, c, s); //对西北块建树temp->q[1] = dfs(r, c+s, s); //对东北块建树temp->q[2] = dfs(r+s, c, s); //对东南块建树temp->q[3] = dfs(r+s, c+s, s); //对西南块建树bool ok = 1; //标记，能否合并for(i = 1; i < 4; i++) //判断能否合并{if(strcmp(temp->q[0]->val, temp->q[i]->val) != 0){ok = 0;break;}}if(ok) //4块能够合并的时候{strcpy(temp->val, temp->q[0]->val);for(i = 0; i < 4; i++){delete temp->q[i];temp->q[i] = NULL; //注意：它必为最后的叶子}}else //不能合并的时候{strcpy(temp->val, "1");}return temp;
}string bfs(quadtree *root) //层次遍历4分树
{int i;string s; //将遍历到的结点的val值都存到ss = "";quadtree *cur = new quadtree;cur = root;queue<quadtree*> que;que.push(root);while(!que.empty()){cur = que.front();que.pop();s = s + cur->val;for(i = 0; i < 4; i++){if(cur->q[i]->val != NULL)que.push(cur->q[i]);}}return s;
}char rec(int x) //映射函数，二进制转十六进制
{char c;switch(x){case 0:c = '0'; break;case 1:c = '1'; break;case 2:c = '2'; break;case 3:c = '3'; break;case 4:c = '4'; break;case 5:c = '5'; break;case 6:c = '6'; break;case 7:c = '7'; break;case 8:c = '8'; break;case 9:c = '9'; break;case 10:c = 'A'; break;case 11:c = 'B'; break;case 12:c = 'C'; break;case 13:c = 'D'; break;case 14:c = 'E'; break;case 15:c = 'F'; break;}return c;
}
int main()
{int k, N, i, j, sum;cin>>k;while(k--){cin>>N;for(i = 0; i < N; i++)for(j = 0; j < N; j++)cin>>MAP[i][j];quadtree *root;root = dfs(0, 0, N);string s;s = bfs(root);int len = s.length(); //获得序列的长度int yu = len % 4; //计算最前面剩余多少个字符if(yu == 1) //当最前面剩余1个字符的时候{cout<<s[0];for(i = 1; i <= len-4; i=i+4){sum = (s[i]-'0')*8 + (s[i+1]-'0')*4 + (s[i+2]-'0')*2 + (s[i+3]-'0');cout<<rec(sum);}}else if(yu == 2) //当最前面剩余2个字符的时候{sum = (s[0]-'0')*2 + s[1]-'0';cout<<rec(sum);for(i = 2; i <= len-4; i=i+4){sum = (s[i]-'0')*8 + (s[i+1]-'0')*4 + (s[i+2]-'0')*2 + (s[i+3]-'0');cout<<rec(sum);}}else if(yu == 3) //当最前面剩余3个字符的时候{sum = (s[0]-'0')*4 + (s[1]-'0')*2 + s[2]-'0';cout<<rec(sum);for(i = 3; i <= len-4; i=i+4){sum = (s[i]-'0')*8 + (s[i+1]-'0')*4 + (s[i+2]-'0')*2 + (s[i+3]-'0');cout<<rec(sum);}}else //当序列长度刚好是4的倍数的时候{for(i = 0; i <= len-4; i=i+4){sum = (s[i]-'0')*8 + (s[i+1]-'0')*4 + (s[i+2]-'0')*2 + (s[i+3]-'0');cout<<rec(sum);}}cout<<endl;}return 0;
}