题目描述
给定一幅包含若干个骰子的图像，图像由三种像素值组成：背景（.）、骰子面（*）和骰子上的点（X）。像素之间的连通性定义为上下左右相邻（共享边），共享角不算连通。骰子是背景像素以外的最大连通区域，每个骰子区域内的X像素组成的连通区域代表一个点。需要统计每个骰子上的点数，并按升序输出所有骰子的点数。
输入格式
输入包含多幅图像。每幅图像的第一行为两个整数www和hhh（5≤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//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;chargrid[60][60];intw,h;voidlabel(inti,intj){if(i>=0&&i<h&&j>=0&&j<w){if(grid[i][j]=='*'||grid[i][j]=='X'){if(grid[i][j]=='*')grid[i][j]='.';elsegrid[i][j]='1';label(i+1,j);label(i-1,j);label(i,j+1);label(i,j-1);}}}voidcover(inti,intj){if(i>=0&&i<h&&j>=0&&j<w&&grid[i][j]=='1'){grid[i][j]='.';cover(i+1,j);cover(i-1,j);cover(i,j+1);cover(i,j-1);}}voidflip(inti,intj){if(i>=0&&i<h&&j>=0&&j<w&&grid[i][j]=='X'){grid[i][j]='.';flip(i+1,j);flip(i-1,j);flip(i,j+1);flip(i,j-1);}}intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intthrows=0;while(cin>>w>>h,w){for(inti=0;i<h;i++)for(intj=0;j<w;j++)cin>>grid[i][j];vector<int>dices;for(inti=0;i<h;i++)for(intj=0;j<w;j++)if(grid[i][j]=='*'){label(i,j);intdice=0;for(intx=0;x<h;x++)for(inty=0;y<w;y++)if(grid[x][y]=='1'){dice++;cover(x,y);}dices.push_back(dice);}for(inti=0;i<h;i++)for(intj=0;j<w;j++)if(grid[i][j]=='X'){dices.push_back(1);flip(i,j);}sort(dices.begin(),dices.end());cout<<"Throw "<<++throws<<'\n';for(inti=0;i<dices.size();i++){if(i>0)cout<<' ';cout<<dices[i];}cout<<"\n\n";}return0;}总结
本题通过两次四连通区域标记，分别识别骰子和骰子上的点，实现了图像中骰子点数的统计。关键点包括：
- 正确实现递归的连通区域填充（注意避免栈溢出，但50×5050 \times 5050×50的深度安全）。
- 区分
*和X的角色，在标记骰子时将X临时改为1，以便后续单独统计点。 - 处理孤立
X的情况，将其视为一个骰子（点数111）。 - 输出时按升序排列所有点数。
该解法是典型的图像处理连通分量分析，适用于小规模图像。