题意分析

题目要求我们根据给定的四叉树编码规则，解码被加密的图像。四叉树编码是一种将图像递归划分为四个象限的数据结构，每个节点代表一个区域。加密过程会重新排序四个子节点的顺序，但顺序由密码和节点编号决定。通过分析测试图像的四叉树编码（其像素值已知），我们可以推断出加密时的子节点顺序，从而解码其他被相同密码加密的图像。

关键点：

1. 四叉树结构：每个节点有四个子节点，分别代表四个象限（左上、右上、左下、右下）。
2. 加密方式：加密时子节点的顺序会被重新排列，顺序由密码和节点编号决定。
3. 测试图像：测试图像的像素值已知（从 0 到 ( n^2 - 1 ) 递增），通过其四叉树编码可以推断加密时的子节点顺序。
4. 解码目标：利用测试图像的四叉树编码信息，解码其他被相同密码加密的图像。

解题思路

1. 四叉树重建：

   • 根据测试图像的四叉树编码，重建其四叉树结构，记录每个叶子节点的编号和对应的像素值。
   • 根据测试图像的已知像素值（从 0 开始递增），推断加密时子节点的顺序。

2. 解码秘密图像：

   • 使用相同的四叉树结构（即相同的子节点顺序）解码秘密图像的四叉树编码。
   • 将秘密图像的叶子节点值映射到对应的像素位置。

3. 输出解码图像：

   • 按照行优先顺序输出解码后的像素值，每个值占 4 个字符宽度，右对齐。

数学表达

• 设测试图像的四叉树叶子节点集合为 ( T )，秘密图像的叶子节点集合为 ( S )。
• 对于测试图像，已知每个叶子节点 ( k ) 对应的像素值 ( p )，可以推断加密时的子节点顺序。
• 对于秘密图像，利用相同的子节点顺序，将叶子节点 ( k ) 的值 ( v ) 映射到对应的像素位置 ( (i, j) )。

解决代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <map>
 
using namespace std;
typedef pair<int,int> pa;
 
int arr[300],raw[20][20],board[20][20],n,k,kcase;
map<int,int> ma;
void create(int arr[][20],pa le=make_pair(1,1),int len=n,int node=0);
 
int main(){
    ios_base::sync_with_stdio(false);
    int times;
    cin>>times;
    while(times--){
        cout<<"Case "<<++kcase<<endl<<endl;
        cin>>n;
        cin>>k;
        for(int i=0,a,b;i<k;++i)
            cin>>a>>b,ma.insert(make_pair(a,b));
        create(raw);
        ma.clear();
        cin>>k;
        for(int i=0,a,b;i<k;++i)
            cin>>a>>b,ma.insert(make_pair(a,b));
        create(board);
        ma.clear();
 
        for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            arr[raw[i][j]]=board[i][j];
 
        for(int i=1,tmp=0;i<=n;++i){
            for(int j=1;j<=n;++j)
                cout<<setw(4)<<arr[tmp++];
            cout<<endl;
        }
        cout<<endl;
    }
    return 0;
}
 
void create(int arr[][20],pa le,int len,int node){
    if(ma.find(node)!=ma.end()){
        int tmp=ma[node];
        for(int i=0;i<len;++i)
        for(int j=0;j<len;++j)
            arr[le.first+i][le.second+j]=tmp;
    }else{
        create(arr,le,(len>>1),(node<<2)+1);
        create(arr,make_pair(le.first+(len>>1),le.second),(len>>1),(node<<2)+2);
        create(arr,make_pair(le.first,(le.second)+(len>>1)),(len>>1),(node<<2)+3);
        create(arr,make_pair(le.first+(len>>1),le.second+(len>>1)),(len>>1),(node<<2)+4);
    }
}

代码解释

1. 输入处理：

   • 读取测试用例数量 times。
   • 对于每个测试用例，读取图像大小 n 和测试图像的四叉树编码，存储叶子节点的编号和值到 ma 中。
   • 调用 create 函数重建测试图像的四叉树结构，填充 raw 矩阵。
   • 清空 ma，读取秘密图像的四叉树编码，再次调用 create 填充 board 矩阵。

2. 解码过程：

   • 将 raw 矩阵中的像素值作为索引，board 矩阵中的像素值作为内容，填充到 arr 数组中。
   • 按行优先顺序输出 arr 数组中的值，每个值占 4 个字符宽度，右对齐。

3. 四叉树重建函数 create：

   • 递归处理四叉树节点，如果是叶子节点，则填充对应区域的值。
   • 如果是内部节点，则递归处理四个子节点（左上、右上、左下、右下）。