题目描述在二维网格上绘制了一组轮廓线轮廓线由同一个可打印字符非空格、非下划线_构成。网格中其余位置为空格或标记字符。一个网格区域定义为被闭合轮廓包围的点集其中任意两点可通过水平或垂直路径相连且不穿过任何轮廓。若某区域包含相同的标记字符非空格且非轮廓字符则该区域称为“已标记区域”且一个区域内不能包含不同的标记字符。不同区域的标记字符可以不同。要求编写程序将每个已标记区域用其标记字符填满即区域内的所有空格均替换为该标记字符。输入以一行下划线_结束输出格式与原输入一致。输入格式输入包含多个网格每个网格以一行由下划线组成的行结束。每行最多808080个字符网格最多323232行。各行长度可以不同。输出格式对于每个网格输出填充后的完整网格包括分隔行、空行以及可能的前导或尾随空格格式与原输入相同。样例输入XXXXXXXXXXXXXXXXXXXX X X X X X X X # # X XXXXXXXX / X X X X X X X X X XXXXXXXXXXXXXXXXXXXX _____________________________ XXXXXXXXXXXX XXXXXX X # XXX XXX X X X X XX X X X X X X X X X XXXXXXX X XXXXXXX X X XX X X X X X X X X X X XXXX X XXXXXXXX XX XXXX X X X X X X / X X X X / X XXXXXXXXXXXXX XXXXXXXX _____________________________样例输出XXXXXXXXXXXXXXXXXXXX X######X X X######X X X######X X X######X X XXXXXXXX / X X######X X X######X X X######X X X######X X XXXXXXXXXXXXXXXXXXXX _____________________________ XXXXXXXXXXXX XXXXXX X########## XXX XXX X X X X XX X X X X X X X X X XXXXXXX X XXXXXXX X X XX X X X X X X X X X X XXXX X XXXXXXXX XX XXXX X X X X X X / X X X X / X XXXXXXXXXXXXX XXXXXXXX _____________________________题目分析轮廓由同一字符wallwallwall构成将网格划分为若干四连通区域。区域内的空格可能未标记仅含空格或已标记含至少一个标记字符。标记字符可以是除空格和wallwallwall之外的任何字符。要求将已标记区域内的所有空格替换为该区域的标记字符。区域的定义是四连通的水平或垂直路径且路径不能穿过轮廓。因此对于每个标记字符从其位置开始进行四方向Flood Fill\texttt{Flood Fill}Flood Fill将连通的空格替换为该标记字符但填充过程不能跨越轮廓即遇到wallwallwall停止。因为wallwallwall是同一字符而标记字符可能各不相同所以需要多次Flood Fill\texttt{Flood Fill}Flood Fill每次从一个标记字符出发。解题思路实现步骤确定如下步骤1\texttt{1}1. 读取整个网格直到遇到以_开头的行。将每行存入二维字符数组maze\textit{maze}maze行末尾添加换行符\n以标记行结束。同时记录轮廓字符wallwallwall即第一个非空字符。步骤2\texttt{2}2. 扫描网格中的每个字符。若该字符不是空格且不是wallwallwall则该字符是一个标记字符ccc。将该位置临时改为空格以避免影响填充然后以该位置为起点执行Flood Fill\texttt{Flood Fill}Flood Fill将所有四方向连通的空格替换为ccc。注意填充过程中遇到wallwallwall或已填充的字符包括其他标记应停止但初始位置已改为空格所以可正常填充。由于同一个区域可能有多个相同的标记字符多次出发会导致重复填充但效果相同。为避免重复可在填充后继续扫描但同一标记字符在不同位置会再次触发填充可能会造成二次染色但第二次填充时空格已经被替换因此不会再有空格可填充所以无影响。不过若同一区域有两个不同标记字符非法输入可能会互相覆盖但题目保证不会出现。步骤3\texttt{3}3. 输出填充后的网格按行输出直到行末换行符。注意保留原输入中的前导空格和尾随空格输出时每行应输出到最后一个非空格字符实际上输出格式要求与原输入相同包括空格和空行因此应按原行长度输出。代码中通过检查maze[i][j] \n来结束该行输出。步骤4\texttt{4}4. 输出分隔行下划线行。该算法的时间复杂度为O(R×C×标记字符数)O(R \times C \times \text{标记字符数})O(R×C×标记字符数)但每个空格最多被填充一次总体为O(R×C)O(R \times C)O(R×C)空间复杂度O(R×C)O(R \times C)O(R×C)。代码实现// Grid Colouring// UVa ID: 785// Verdict: Accepted// Submission Date: 2016-12-01// UVa Run Time: 0.110s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;charmaze[35][85];intoffset[4][2]{{-1,0},{1,0},{0,-1},{0,1}};voidflood_fill(inti,intj,charold,charreplaced){if(i0i35j0j85maze[i][j]old){maze[i][j]replaced;for(intk0;k4;k)flood_fill(ioffset[k][0],joffset[k][1],old,replaced);}}intmain(intargc,char*argv[]){string line;while(getline(cin,line)){memset(maze, ,sizeof(maze));introws0;charwall0;do{for(inti0;iline.length();i){maze[rows][i]line[i];if(wall0line[i]! )wallline[i];}maze[rows][line.length()]\n;}while(getline(cin,line),line.front()!_);for(inti0;irows;i)for(intj0;j85;j){if(maze[i][j]\n)break;if(maze[i][j]!wallmaze[i][j]! ){charreplacedmaze[i][j];maze[i][j] ;flood_fill(i,j, ,replaced);}}for(inti0;irows;i)for(intj0;j85;j){coutmaze[i][j];if(maze[i][j]\n)break;}coutline\n;}return0;}总结本题通过对已标记区域执行Flood Fill\texttt{Flood Fill}Flood Fill将区域内空格替换为标记字符实现网格着色。关键在于识别轮廓字符和标记字符并保证填充不跨越轮廓。由于每个区域最多被填充一次且填充操作直接修改原数组效率较高。输出时需保留原格式包括行内空格和换行符。该解法是模拟类问题的典型应用展示了Flood Fill\texttt{Flood Fill}Flood Fill在区域填充中的灵活性。