UVa 776 Monkeys in a Regular Forest

题目描述在一片规则的欧几里得网格森林中每个格点生长一棵树每棵树属于nnn个物种之一由单个字符表示例如A、B、C等。如果两棵相同物种的树在八个方向水平、垂直或对角上相邻则认为它们是邻居。一群专门的猴子按顺序释放每群猴子会占据一片由同物种树组成的连通区域且该区域尚未被其他猴子群占据。释放顺序为从左到右、从上到下即按行优先扫描。给定森林地图需要为每个格子分配一个整数编号表示该格子所属的猴子家庭编号从111开始连续编号。输出时每列的数字右对齐列宽为该列最大数字的位数。每个实例的输出以单独一行%结束。输入格式输入包含多个矩阵实例。每个矩阵由若干行组成每行包含由单个空格分隔的字符可能包含大小写字母。一个实例的结束由单独一行%标记。下一个实例紧接着%行之后继续。输入可能以文件结束终止且最后一个实例可能没有%行但仍需输出。输出格式对于每个矩阵输出若干行每行包含对应格子的整数编号数字之间用单个空格分隔且每列右对齐。每列宽度为该列所有数字中最大值的十进制位数。每个实例输出后输出一行%。样例输入A B D E C C D F F W D D D D P W E W W W % a A b B c d E t a a a a a c c t e f g h c a a t样例输出1 2 3 4 5 5 3 6 6 7 3 3 3 3 8 7 9 7 7 7 % 1 2 3 4 5 6 7 8 1 1 1 1 1 5 5 8 9 10 11 12 5 1 1 8 %题目分析本题本质是对二维字符矩阵进行连通块标记但连通性定义为八方向上下左右及对角线且仅相同字符视为连通。释放顺序为行优先从第000行开始从左到右扫描每个格子若该格子尚未被标记则以它为起点用Flood Fill\texttt{Flood Fill}Flood Fill将整个同字符连通块标记为一个新的编号。由于编号按扫描顺序递增且扫描顺序固定输出即为满足题意的家庭编号。需要注意输出格式每一列的数字必须右对齐列宽为该列最大数字的位数。因此需要在编号完成后统计每一列的最大值再按格式输出。解题思路实现步骤确定如下步骤1\texttt{1}1. 读取输入。由于每行由空格分隔的字符组成使用getline\texttt{getline}getline逐行读取。对每一行跳过空格提取字母字符存入二维数组maze\textit{maze}maze并记录列数columns\textit{columns}columns。遇到单独一行%时表示当前实例输入结束进入处理阶段。步骤2\texttt{2}2. 处理当前实例。初始化编号矩阵number\textit{number}number为000。按行优先顺序iii从000到rows−1\textit{rows}-1rows−1jjj从000到columns−1\textit{columns}-1columns−1遍历若maze[i][j]\textit{maze}[i][j]maze[i][j]不是已标记的占位符例如0则执行floodFill\texttt{floodFill}floodFill函数将与该格子八方向相连通且字符相同的所有格子均标记为当前编号nnn并记录每列的最大编号值用于后续宽度计算。编号nnn自增。步骤3\texttt{3}3. 计算每列的输出宽度。对每一列jjj统计maxWidth[j]\textit{maxWidth}[j]maxWidth[j]为number\textit{number}number矩阵中该列最大值的十进制位数。步骤4\texttt{4}4. 输出。对于每一行iii输出该行每个格子的编号使用setw\texttt{setw}setw控制宽度右对齐数字间用一个空格分隔。输出完所有行后输出一行%。步骤5\texttt{5}5. 清空当前实例的数据继续读取下一个实例。若文件结束前还有未处理的数据即最后没有%行则同样进行处理。该算法时间复杂度为O(rows×columns)O(\text{rows} \times \text{columns})O(rows×columns)空间复杂度相同完全满足输入规模限制矩阵行列数未明确但通常较小。代码实现// Monkeys in a Regular Forest// UVa ID: 776// Verdict: Accepted// Submission Date: 2017-10-23// UVa Run Time: 0.010s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintMAXV1010;charmaze[MAXV][MAXV];intnumber[MAXV][MAXV];introws0,columns0,maxWidth[MAXV];intoffsetx[8]{0,0,1,1,1,-1,-1,-1};intoffsety[8]{1,-1,0,1,-1,0,1,-1};voidfloodFill(inti,intj,charold,intn){if(i0irowsj0jcolumnsmaze[i][j]old){maze[i][j]0,number[i][j]n;maxWidth[j]max(maxWidth[j],n);for(intk0;k8;k)floodFill(ioffsetx[k],joffsety[k],old,n);}}voidrelease(){memset(maxWidth,0,sizeof(maxWidth));intn1;for(inti0;irows;i)for(intj0;jcolumns;j)if(maze[i][j]!0){floodFill(i,j,maze[i][j],n);n;}for(inti0;icolumns;i){intspaces0;while(maxWidth[i]0){spaces;maxWidth[i]/10;}maxWidth[i]spaces;}for(inti0;irows;i){for(intj0;jcolumns;j){if(j)cout ;coutsetw(maxWidth[j])rightnumber[i][j];}cout\n;}cout%\n;}intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);string line;while(getline(cin,line)){if(line!%){columns0;for(inti0;iline.length();i)if(isalpha(line[i]))maze[rows][columns]line[i];rows;continue;}release();rows0;}if(rows0)release();return0;}总结本题通过Flood Fill\texttt{Flood Fill}Flood Fill标记八方向连通块并按照行优先顺序分配编号直接模拟了猴子家庭的释放过程。输出格式要求列右对齐可通过统计每列最大数字的位数并利用setw\texttt{setw}setw实现。输入解析时需注意%作为实例结束标记以及最后可能缺少结束标记的情况。该解法简洁高效充分利用了连通块标记和格式化输出的技巧是典型的模拟与连通性处理相结合的问题。