通过这道题练习了下四叉树，其实很简单，把四叉树当成多叉树构建就可以了，还一个很经典的应用就是Trie（字典树），方法有动态和静态的，对于二叉树和四叉树索引上有规律，可以借此采用静态的方法，快速编码。
而这道题就是给张N*N的图，然后对此图生成一颗四叉树，构成一颗编码用的树。构建该四叉树的复杂度为O(M),M=N^2，M为图中元素的个数，复杂度级别和四叉树节点数成线性关系，剩下，对于本题，就是模拟了，代码如下：
#include <iostream> #include <vector> #include <string> using namespace std; const int MAXN = 600; class CNODE { public: int X, Y, E; int flag, num; public: CNODE() {} CNODE(int _x, int _y, int _e, int _f, int _n) : X(_x), Y(_y), E(_e), flag(_f), num(_n) {} }node[MAXN * MAXN * 2]; int bin_map[MAXN][MAXN]; class CQUADTREE { public: public: CQUADTREE() {} void Build(int r, int x, int y, int e) { if(e > 1) { Build(4 * r - 2, x, y, e / 2); Build(4 * r - 1, x, y + e / 2, e / 2); Build(4 * r, x + e / 2, y, e / 2); Build(4 * r + 1, x + e / 2, y + e / 2, e / 2); int i, judge = 0; for(i = 4 * r - 2; i < 4 * r + 2; i++) { if(node[i].flag) break; judge |= (1 << node[i].num); if(judge == 3) break; } if(i < 4 * r + 2) node[r] = CNODE(x, y, e, 1, -1); else node[r] = CNODE(x, y, e, 0, bin_map[x][y]); } else //叶子 { node[r] = CNODE(x, y, e, 0, bin_map[x][y]); } } }; void go(int n) { CQUADTREE tree; tree.Build(1, 0, 0, n); vector<int> Q; string ans = ""; Q.push_back(1); for(int i = 0; i < Q.size(); i++) { if(node[Q[i]].flag) { ans += "1"; for(int j = 4 * Q[i] - 2; j < 4 * Q[i] + 2; j++) Q.push_back(j); } else { ans += "0"; if(node[Q[i]].num) ans += "1"; else ans += "0"; } } //cout << ans << endl; while(ans.length() % 4) ans = "0" + ans; for(int i = 0; i < ans.length(); i += 4) { int tmp = 8 * (ans[i] - '0') + 4 * (ans[i + 1] - '0') + 2 * (ans[i + 2] - '0') + 1 * (ans[i + 3] - '0'); printf("%X", tmp); } printf("\n"); } int main() { int T; scanf("%d", &T); while(T--) { int n; scanf("%d", &n); for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) scanf("%d", &bin_map[i][j]); go(n); } }转载于:https://www.cnblogs.com/litstrong/archive/2011/03/14/1984184.html
