当前位置: 代码迷 >> 综合 >> zoj - 1788 - Quad Trees(四分树)
  详细解决方案

zoj - 1788 - Quad Trees(四分树)

热度:76   发布时间:2024-01-10 14:05:14.0

题意:输入一个整数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;
}