题目描述给定一个用四叉树Quadtree\texttt{Quadtree}Quadtree表示的2m×2m2^m \times 2^m2m×2m黑白栅格图像其中mmm为正整数图像最大尺寸为256×256256 \times 256256×256要求将其转换为游程编码Run Length Code\texttt{Run Length Code}Run Length Code。游程编码中像素按从左下角开始、逐行向上扫描的顺序排列第一组假定为全黑即连续黑色像素的个数随后交替记录白色和黑色像素的连续个数。已知四叉树的节点描述采用递归方式每个节点要么是叶子标记为F或E要么拥有四个子节点子节点以编号索引形式给出。输入保证根节点为节点111。输入格式第一行为一个正整数TTT表示测试用例个数。之后每个测试用例的第一行为图像边长LLLLLL是222的幂第二行为节点总数NNN。接下来NNN行每行描述一个节点从节点111开始每行包含四个字段每个字段要么是字符F满、E空要么是一个正整数表示该子节点的编号。输出格式对于每个测试用例输出一行包含游程编码的所有整数用空格分隔。相邻两个测试用例的输出之间需要输出一个空行。样例输入1 8 5 E 2 F 3 E E F F 4 5 E E F E E F F E E E输出0 20 4 4 9 1 1 1 4 1 1 2 4 4 4 4题目分析本题的核心任务是将四叉树结构还原为实际的像素矩阵然后按从左下到右上的逐行扫描顺序生成游程编码。四叉树的每个内部节点代表一个正方形区域该区域被等分为四个大小相等的子区域子区域顺序固定为左下、右下、左上、右上。当某个子区域完全为黑色或完全为白色时对应叶子标记为F或E否则该子区域由另一个内部节点表示并给出其编号。输入中每个节点的四个字段顺序固定分别对应四个子区域。叶子节点直接给出颜色内部节点给出子节点编号。根节点编号固定为111且整个图像的大小LLL是222的幂。直接递归填充像素矩阵是直观且高效的方法。由于图像最大为256×256256 \times 256256×256总像素数为655366553665536可以轻松存储为一个一维数组。填充完成后按扫描顺序遍历数组统计连续相同颜色的长度交替记录即可。注意游程编码的第一组固定为黑色F即使图像开始部分是白色也需先输出0然后输出白色像素的个数。解题思路数据结构使用结构体存储每个节点的四个子项信息child[4]存储子节点编号若为000表示该子项是叶子。leafVal[4]仅当对应child为000时有效true表示该子区域全黑false表示全白。递归填充图像从根节点出发每次处理一个正方形区域由左下角坐标(x,y)(x, y)(x,y)和边长size确定。对于当前节点遍历四个子区域顺序固定若子节点为叶子则将该子区域所有像素填充为相应颜色黑 / 白否则递归处理子节点。由于四叉树的划分保证了每个叶子区域大小是1×11 \times 11×1最终所有像素都会被填充。生成游程编码填充完成后得到一个长度为L×LL \times LL×L的整数数组其中111表示黑000表示白。按照从左下到右上的顺序扫描即外层循环yyy从000到L−1L-1L−1内层循环xxx从000到L−1L-1L−1索引计算为y * L x。扫描过程中统计连续相同颜色的个数当颜色变化时将当前计数存入结果并重置计数为新颜色的第一个像素。扫描结束后将最后一组计数加入结果。由于题目规定游程编码的第一组假定为黑色我们需要从颜色111黑色开始统计。如果第一个像素是白色则第一组计数为000随后输出白色组的长度这与样例输出一致样例输出第一个数是000因为起点是白色。复杂度分析每个叶子填充时时间复杂度正比于叶子区域面积。四叉树的总叶子数量不超过O(L2)O(L^2)O(L2)每次填充叶子内部采用循环总时间复杂度为O(L2)O(L^2)O(L2)因为每个像素恰好被填充一次。扫描生成游程编码也需要O(L2)O(L^2)O(L2)。空间复杂度为O(L2)O(L^2)O(L2)存储像素数组以及O(N)O(N)O(N)存储节点。由于L≤256L \le 256L≤256该解法在时间和空间上均非常充裕。代码实现// 2D Representations// UVa ID: 874// Verdict: Accepted// Submission Date: 2026-06-21// UVa Run Time: 0.030s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structNode{intchild[4];// 子节点索引0表示该子项为叶子boolleafVal[4];// 当 child[i]0 时有效true 表示满(F)false 表示空(E)};intL;// 图像边长vectorNodenodes;// 节点数组下标从1开始// 递归填充图像将四叉树映射到一维像素数组 img (大小为 L*L)// 参数当前节点索引区域左下角坐标 (x, y)区域边长 sizevoidfillImage(vectorintimg,intnodeIdx,intx,inty,intsize){inthalfsize/2;// 四个子区域的偏移量顺序左下、右下、左上、右上intdx[4]{0,half,0,half};intdy[4]{0,0,half,half};for(inti0;i4;i){intnxxdx[i];intnyydy[i];if(nodes[nodeIdx].child[i]0){// 叶子填充该区域全部为对应值intvalnodes[nodeIdx].leafVal[i]?1:0;// 1满0空for(intdy20;dy2half;dy2)for(intdx20;dx2half;dx2)img[(nydy2)*L(nxdx2)]val;}else{// 内部节点递归处理fillImage(img,nodes[nodeIdx].child[i],nx,ny,half);}}}intmain(){intT;cinT;for(intcaseNo0;caseNoT;caseNo){cinL;intN;cinN;nodes.assign(N1,Node());// 读取每个内部节点的四个子项for(inti1;iN;i){for(intj0;j4;j){string token;cintoken;if(tokenF||tokenE){nodes[i].child[j]0;nodes[i].leafVal[j](tokenF);}else{nodes[i].child[j]stoi(token);// leafVal 无需设置}}}// 生成像素数组初始为0空vectorintimage(L*L,0);// 根节点编号为1整个图像区域为 (0,0) 到 (L,L)fillImage(image,1,0,0,L);// 游程编码第一组假设为满(1)vectorintrunLength;intcurVal1;// 当前颜色1满intcnt0;for(inty0;yL;y){for(intx0;xL;x){intpixelimage[y*Lx];if(pixelcurVal){cnt;}else{runLength.push_back(cnt);curValpixel;cnt1;}}}runLength.push_back(cnt);// 最后一组// 输出当前用例的结果for(size_t i0;irunLength.size();i){if(i0)cout ;coutrunLength[i];}coutendl;// 两个连续用例之间输出空行if(caseNo!T-1)coutendl;}return0;}总结本题巧妙地将四叉树数据结构与游程编码相结合本质上是一个树形结构还原与图像扫描的模拟问题。解题的关键在于正确解析输入区分叶子与内部节点。按照固定的子区域顺序进行递归填充确保像素位置正确。扫描顺序为从左下到右上且游程编码的第一组固定为黑色需要初始化当前颜色为黑色即使开头没有黑色像素也会先输出0。通过将四叉树展开为像素矩阵问题被转化为简单的遍历统计代码实现清晰、不易出错。由于图像尺寸较小直接填充矩阵的方法是最高效且最直观的。若图像尺寸极大则需考虑边递归边生成游程编码的优化方案但本题无需如此。
