学步园

题意：输入一个整数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值都存到s
    s = "";
    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;
}