四叉树与超四叉树问题题解

这个问题涉及到四叉树和超四叉树的构建与压缩，主要考察递归分治思想和数据结构优化。

问题分析

四叉树(Quadtree)：

• 用于存储数字图像的数据结构
• 每个节点如果不是纯色，则被划分为四个子节点
• 四个子节点分别对应原区域的左上、右上、左下、右下象限

超四叉树(Super Quadtree)：

• 对四叉树的进一步优化，通过识别重复子树进行压缩
• 当发现相同子树时，用引用代替重复部分，减少节点数量

解题思路

1. 图像预处理：

   • 将输入图像扩展为边长是2的幂的正方形，不足部分用0填充
   • 例如，5x13的图像会被扩展为16x16的图像

2. 四叉树构建：

   • 使用递归方法构建四叉树
   • 每个节点检查其区域是否为纯色，若是则直接存储颜色值
   • 否则将区域划分为四个子区域，递归处理每个子区域

3. 超四叉树优化：

   • 在递归构建四叉树的过程中，记录每个非叶子节点的四个子节点状态
   • 当发现重复的子节点状态时，用引用代替，减少节点数量

代码实现分析

关键数据结构：

struct state{
    int s1,s2,s3,s4;
    bool check(int n1,int n2,int n3,int n4)
    {
        return n1==s1&&n2==s2&&n3==s3&& n4==s4;
    }
}p[10010];
int tot; // 记录不同子树状态的数量
int c1, c2; // 分别记录超四叉树和四叉树的节点数量

递归处理函数：

int dfs(int x1, int y1, int x2, int y2)
{
    int t = c1;
    c1++, c2++; // 为当前节点计数
    
    // 处理叶子节点
    if(x1 == x2 && y1 == y2) return a[x1][y1];
    
    // 划分区域并递归处理四个子区域
    int x3 = (x1 + x2)/2;
    int y3 = (y1 + y2)/2;
    int a1 = dfs(x1, y1, x3, y3);
    int a2 = dfs(x3+1, y1, x2, y3);
    int a3 = dfs(x1, y3+1, x3, y2);
    int a4 = dfs(x3+1, y3+1, x2, y2);
    
    // 检查是否四个子节点都是纯色
    if(a1 == 0 && a2 == 0 && a3 == 0 && a4 == 0)
    {
        c1 = c1 - 4;
        c2 = c2 - 4;
        return 0;
    }
    if(a1 == 1 && a2 == 1 && a3 == 1 && a4 == 1)
    {
        c1 = c1 - 4;
        c2 = c2 - 4;
        return 1;
    }
    
    // 检查是否有重复的子树状态
    for(int i = 2; i < tot; i++)
    {
        if(p[i].check(a1, a2, a3, a4))
        {
            c1 = t; // 撤销新增的节点，使用已有引用
            return i;
        }
    }
    
    // 记录新的子树状态
    p[tot++] = (state){a1, a2, a3, a4};
    return tot - 1;
}

主函数处理流程：

int main()
{
    while(1)
    {
        int n, m;
        cin >> n >> m;
        if(n == 0 && m == 0) break;
        
        // 读取输入图像
        memset(a, 0, sizeof(a));
        for(int i = 0; i < n; i++)
        {
            scanf("%s", s[i]);
            for(int j = 0; j < m; j++)
            {
                a[i][j] = s[i][j] - '0';
            }
        }
        
        // 扩展图像为2的幂次方大小
        int t = max(n, m);
        int k = 1;
        while(k < t) k = k << 1;
        
        // 初始化并进行递归处理
        tot = 2;
        c1 = c2 = 0;
        dfs(0, 0, k-1, k-1);
        
        // 输出结果
        cout << c2 << " " << c1 << endl; 
    }
    return 0;
}

复杂度分析

• 时间复杂度：$O(N^2)$，其中N是扩展后图像的边长。每个像素会被访问一次，每次访问的处理时间为常数。
• 空间复杂度：$O(N^2)$，主要用于存储扩展后的图像和递归调用栈。

这个算法通过递归分治和状态记录，高效地构建了四叉树并进行了超四叉树优化，能够在合理时间内处理较大的输入图像。