题目描述给定一幅包含若干个骰子的图像图像由三种像素值组成背景.、骰子面*和骰子上的点X。像素之间的连通性定义为上下左右相邻共享边共享角不算连通。骰子是背景像素以外的最大连通区域每个骰子区域内的X像素组成的连通区域代表一个点。需要统计每个骰子上的点数并按升序输出所有骰子的点数。输入格式输入包含多幅图像。每幅图像的第一行为两个整数www和hhh5≤w,h≤505 \le w, h \le 505≤w,h≤50表示图像的宽度和高度。接下来hhh行每行www个字符字符为.、*或X。输入以0 0结束。输出格式对于每幅图像输出两行第一行为Throw X:其中XXX为图像编号从111开始第二行为该图像中所有骰子的点数按升序排列用空格分隔。每组输出后跟一个空行。样例输入30 15 .............................. .............................. ...............*.............. ...*****......****............ ...*X***.....**X***........... ...*****....***X**............ ...***X*.....****............. ...*****.......*.............. .............................. ........***........******..... .......**X****.....*X**X*..... ......*******......******..... .....****X**.......*X**X*..... ........***........******..... .............................. 0 0输出Throw 1 1 2 2 4题目分析本题的核心是连通区域标记Connected Component Labeling\texttt{Connected Component Labeling}Connected Component Labeling。需要先找到所有骰子区域由*和X组成的连通区域然后对每个骰子区域统计其中X像素的连通区域数量即为该骰子的点数。由于骰子区域可能包含多个点点之间由*像素隔开因此X像素的连通区域数量就是点数。算法分两步识别骰子从任意*像素开始四连通地遍历所有*和X像素将访问过的*标记为.背景将X暂时标记为1表示已访问但尚未统计点。统计点数在标记的骰子区域内对每个1像素即原X像素进行连通区域搜索每找到一个连通的1区域点数加111并将该区域全部标记为.。收集点数排序输出。注意可能有X像素不属于任何*区域但题目保证每个骰子至少有一个点且X必在骰子内部因此无需额外处理但代码中最后遍历所有未处理的X若存在则视为一个骰子点数111。解题思路读取图像存入二维字符数组grid。主循环遍历所有像素当遇到*时调用label函数将该骰子的所有像素标记*变为.X变为1。统计点数在标记区域中遍历所有1每找到一个调用cover函数将该1连通区域全部变为.并计数加111。处理孤立点若存在X未被上述过程处理即不属于任何*区域则视为一个点数为111的骰子调用flip将其置为.。排序输出收集所有点数排序后输出。复杂度分析每个像素最多被访问常数次时间复杂度O(w⋅h)O(w \cdot h)O(w⋅h)w,h≤50w, h \le 50w,h≤50。空间复杂度O(w⋅h)O(w \cdot h)O(w⋅h)。代码实现// The Die is Cast// UVa ID: 657// Verdict: Accepted// Submission Date: 2016-08-27// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;chargrid[60][60];intw,h;voidlabel(inti,intj){if(i0ihj0jw){if(grid[i][j]*||grid[i][j]X){if(grid[i][j]*)grid[i][j].;elsegrid[i][j]1;label(i1,j);label(i-1,j);label(i,j1);label(i,j-1);}}}voidcover(inti,intj){if(i0ihj0jwgrid[i][j]1){grid[i][j].;cover(i1,j);cover(i-1,j);cover(i,j1);cover(i,j-1);}}voidflip(inti,intj){if(i0ihj0jwgrid[i][j]X){grid[i][j].;flip(i1,j);flip(i-1,j);flip(i,j1);flip(i,j-1);}}intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intthrows0;while(cinwh,w){for(inti0;ih;i)for(intj0;jw;j)cingrid[i][j];vectorintdices;for(inti0;ih;i)for(intj0;jw;j)if(grid[i][j]*){label(i,j);intdice0;for(intx0;xh;x)for(inty0;yw;y)if(grid[x][y]1){dice;cover(x,y);}dices.push_back(dice);}for(inti0;ih;i)for(intj0;jw;j)if(grid[i][j]X){dices.push_back(1);flip(i,j);}sort(dices.begin(),dices.end());coutThrow throws\n;for(inti0;idices.size();i){if(i0)cout ;coutdices[i];}cout\n\n;}return0;}总结本题通过两次四连通区域标记分别识别骰子和骰子上的点实现了图像中骰子点数的统计。关键点包括正确实现递归的连通区域填充注意避免栈溢出但50×5050 \times 5050×50的深度安全。区分*和X的角色在标记骰子时将X临时改为1以便后续单独统计点。处理孤立X的情况将其视为一个骰子点数111。输出时按升序排列所有点数。该解法是典型的图像处理连通分量分析适用于小规模图像。