当前位置：首页 > news >正文

UVa 657 The Die is Cast

news 2026/7/12 11:41:45

题目描述

给定一幅包含若干个骰子的图像，图像由三种像素值组成：背景（.）、骰子面（*）和骰子上的点（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;}