题目描述给定一个由可打印字符非*、#、.和空格构成的轮廓线轮廓闭合形成一个单一的非空区域。轮廓是八连通的水平、垂直、对角线。轮廓上的字符可以任意选择例如图中的X。另有一个星号*标记位于轮廓内部或外部指示需要填充的一侧。填充操作为将与星号同侧即从星号位置开始四方向扩展且与轮廓边界相邻的空格替换为#替换的规则是一个空格若其上下左右任一邻居不是空格也不是#即轮廓字符则该空格被涂成#。填充完成后星号被移除。要求输出填充后的网格保留原轮廓字符且每行输出到最后一个非空格字符为止。输入包含多个测试用例每个测试用例以一行由下划线_组成的行结束。输入格式输入第一行为一个整数NNN表示测试用例个数。随后NNN个测试用例每个用例由若干行组成每行包含网格的一行可能包含空格。网格中包括轮廓字符非空格、非*、非#、非.的任意可打印字符、空格表示背景以及一个星号*表示填充侧。网格行数以一行至少一个下划线_组成的行结束该行不包含在网格中。输出格式对于每个测试用例输出填充后的网格。每行输出到该行最后一个非空格字符为止即去除尾随空格。每个测试用例输出后原样输出结束行即下划线行。样例输入1 XXXXXXXX XX X X X XXXXXXXX X X X X X *XX XXXXXXXXXX -样例输出XXXXXXXX X####X X X XXXXXXXX X#######XX X#### # #XX X#######XX XXXXXXXXXX ########XX X#######X #XX XXXXXXXXXX -题目分析轮廓由给定字符组成形成闭合区域。星号*位于区域内或区域外指示需要填充的一侧。填充区域定义为从星号位置开始四方向扩展到的所有空格且这些空格至少有一个四方向邻居是轮廓字符即非空格且非#的非轮廓字符。该条件确保只填充紧邻轮廓边界的一层空格而不是整个内部区域。实际上由于轮廓闭合星号一侧的所有空格都满足该条件但根据题意只有与轮廓相邻的空格才被涂黑且是单层填充。因此算法只需从星号位置开始进行四方向Flood Fill\texttt{Flood Fill}Flood Fill但填充的条件是当前空格至少有一个四方向邻居是轮廓字符而不是简单地填充所有可达空格。更准确的理解填充操作是在轮廓的指定一侧增加一层#标记使得每个被涂黑的格子都紧邻轮廓。因此从星号位置出发对空格进行四方向搜索若当前空格满足“至少一个四方向邻居是轮廓字符”则将其改为#并继续搜索其四方向相邻空格。但若已改为#则其邻居可能不再是空格需谨慎处理。另一种理解是所有与星号同侧通过空格连通且与轮廓相邻的空格均被涂黑。这等价于从星号开始对空格进行Flood Fill\texttt{Flood Fill}Flood Fill但只标记那些与轮廓相邻的空格并将它们改为#同时继续扩展时已标记为#的格子不再视为空格从而只填充一层。实际上由于我们只判断原始网格中的空格且使用visited防止重复一次填充即可完成。算法步骤为从星号位置开始对空格进行四方向DFS\texttt{DFS}DFS。对于每个访问到的空格检查其上下左右四个邻居是否在网格范围内且不是空格和#即轮廓字符若是则将该空格改为#。然后递归访问四个邻居空格但注意邻居若是#则不再继续。这样所有与星号连通的空格中只有紧邻轮廓的一层被染色因为染成#后其外围空格在递归时仍会被访问但检查时可能满足条件而被染色从而形成多层实际上由于染成#后该格子不再是空格但其相邻的空格在递归时仍会被访问并可能被染色这会导致填充多层的效果。但根据样例和题意填充是在轮廓一侧的一层空格而非多层。因此更正确的做法是只将满足条件的空格改为#但继续向四周扩展空格而不是在#上停止。但由于#不是空格不会再次被访问所以从星号出发的所有连通空格都会被检查只要它们与轮廓相邻就被染色这确实会染色所有与轮廓相邻且与星号同侧的空格可能包括多层实际上如果内部区域有多层空格最外层与轮廓相邻第二层虽然不与轮廓直接相邻但第一层被染色后变为#第二层空格与第一层#相邻但条件要求邻居是轮廓字符非空格且非#所以第二层不会被染色。因此算法结果正好是一层。实现时需注意网格宽度可能因行而异但最大宽度不超过100100100行数不超过404040。解题思路具体实现步骤如下步骤1\texttt{1}1. 读取测试用例个数casescasescases。对每个用例初始化网格数组为空格行数计数器rows0\textit{rows} 0rows0。循环读取行直到遇到以_开头的行可能包含多个下划线。将每行字符存入maze\textit{maze}maze并记录星号位置(stari,starj)(\textit{star}_i, \textit{star}_j)(stari,starj)。步骤2\texttt{2}2. 将星号位置改为空格因为星号仅用于指示起始点不参与输出。步骤3\texttt{3}3. 执行Flood Fill\texttt{Flood Fill}Flood Fill。使用递归函数floodFill(i,j)\texttt{floodFill}(i, j)floodFill(i,j)若(i,j)(i,j)(i,j)在网格范围内且未被访问且为空格则标记为已访问然后检查其上下左右四个邻居若存在邻居是轮廓字符即不是空格也不是#则将当前格子改为#。接着递归访问四个方向邻居。步骤4\texttt{4}4. 输出时对于每一行从右向左找到最后一个非空格字符的位置然后输出该行从开头到该位置的所有字符保留前导空格和中间空格。最后输出结束行即下划线行。注意轮廓字符可能是任意可打印字符除*、#、.和空格因此判断非空格且非#即为轮廓。在填充过程中#作为已填充标记不应再被当作空格处理。代码实现// Contour Painting// UVa ID: 782// Verdict: Accepted// Submission Date: 2017-10-24// UVa Run Time: 0.020s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;charmaze[40][100];introws0,visited[40][100];intoffsetx[4]{0,0,1,-1},offsety[4]{1,-1,0,0};voidfloodFill(inti,intj){if(i0irowsj0j100!visited[i][j]maze[i][j] ){visited[i][j]1;boolflagfalse;for(intk0;k4;k){intnextiioffsetx[k],nextjjoffsety[k];if(nexti0nextirowsnextj0nextj100){if(maze[nexti][nextj]! maze[nexti][nextj]!#){flagtrue;break;}}}if(flag)maze[i][j]#;for(intk0;k4;k)floodFill(ioffsetx[k],joffsety[k]);}}intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intcases;cincases;cin.ignore(1024,\n);string line;for(intc1;ccases;c){rows0;memset(maze, ,sizeof(maze));intstari,starj;while(getline(cin,line),line.front()!_){for(inti0;iline.length();i){maze[rows][i]line[i];if(line[i]*){starirows;starji;}}rows;}maze[stari][starj] ;memset(visited,0,sizeof(visited));floodFill(stari,starj);for(inti0;irows;i){for(intcolumns99;columns0;columns--){if(maze[i][columns]! ){for(intj0;jcolumns;j)coutmaze[i][j];break;}}cout\n;}coutline\n;}return0;}总结本题通过Flood Fill\texttt{Flood Fill}Flood Fill在指定侧为轮廓添加一层#填充。核心在于判断条件空格只要与轮廓字符相邻则被涂色。由于访问标记和染色同步进行确保只填充一层。输入输出格式需注意每行尾部空格的去除以及结束行下划线行的保留。该算法时间复杂度O(R×C)O(R \times C)O(R×C)空间O(R×C)O(R \times C)O(R×C)适用于网格大小有限的场景。此类问题体现了图像处理中边界填充的模拟思路。 UVa 782 Contour Painting
题目描述给定一个由可打印字符非*、#、.和空格构成的轮廓线轮廓闭合形成一个单一的非空区域。轮廓是八连通的水平、垂直、对角线。轮廓上的字符可以任意选择例如图中的X。另有一个星号*标记位于轮廓内部或外部指示需要填充的一侧。填充操作为将与星号同侧即从星号位置开始四方向扩展且与轮廓边界相邻的空格替换为#替换的规则是一个空格若其上下左右任一邻居不是空格也不是#即轮廓字符则该空格被涂成#。填充完成后星号被移除。要求输出填充后的网格保留原轮廓字符且每行输出到最后一个非空格字符为止。输入包含多个测试用例每个测试用例以一行由下划线_组成的行结束。输入格式输入第一行为一个整数NNN表示测试用例个数。随后NNN个测试用例每个用例由若干行组成每行包含网格的一行可能包含空格。网格中包括轮廓字符非空格、非*、非#、非.的任意可打印字符、空格表示背景以及一个星号*表示填充侧。网格行数以一行至少一个下划线_组成的行结束该行不包含在网格中。输出格式对于每个测试用例输出填充后的网格。每行输出到该行最后一个非空格字符为止即去除尾随空格。每个测试用例输出后原样输出结束行即下划线行。样例输入1 XXXXXXXX XX X X X XXXXXXXX X X X X X *XX XXXXXXXXXX -样例输出XXXXXXXX X####X X X XXXXXXXX X#######XX X#### # #XX X#######XX XXXXXXXXXX ########XX X#######X #XX XXXXXXXXXX -题目分析轮廓由给定字符组成形成闭合区域。星号*位于区域内或区域外指示需要填充的一侧。填充区域定义为从星号位置开始四方向扩展到的所有空格且这些空格至少有一个四方向邻居是轮廓字符即非空格且非#的非轮廓字符。该条件确保只填充紧邻轮廓边界的一层空格而不是整个内部区域。实际上由于轮廓闭合星号一侧的所有空格都满足该条件但根据题意只有与轮廓相邻的空格才被涂黑且是单层填充。因此算法只需从星号位置开始进行四方向Flood Fill\texttt{Flood Fill}Flood Fill但填充的条件是当前空格至少有一个四方向邻居是轮廓字符而不是简单地填充所有可达空格。更准确的理解填充操作是在轮廓的指定一侧增加一层#标记使得每个被涂黑的格子都紧邻轮廓。因此从星号位置出发对空格进行四方向搜索若当前空格满足“至少一个四方向邻居是轮廓字符”则将其改为#并继续搜索其四方向相邻空格。但若已改为#则其邻居可能不再是空格需谨慎处理。另一种理解是所有与星号同侧通过空格连通且与轮廓相邻的空格均被涂黑。这等价于从星号开始对空格进行Flood Fill\texttt{Flood Fill}Flood Fill但只标记那些与轮廓相邻的空格并将它们改为#同时继续扩展时已标记为#的格子不再视为空格从而只填充一层。实际上由于我们只判断原始网格中的空格且使用visited防止重复一次填充即可完成。算法步骤为从星号位置开始对空格进行四方向DFS\texttt{DFS}DFS。对于每个访问到的空格检查其上下左右四个邻居是否在网格范围内且不是空格和#即轮廓字符若是则将该空格改为#。然后递归访问四个邻居空格但注意邻居若是#则不再继续。这样所有与星号连通的空格中只有紧邻轮廓的一层被染色因为染成#后其外围空格在递归时仍会被访问但检查时可能满足条件而被染色从而形成多层实际上由于染成#后该格子不再是空格但其相邻的空格在递归时仍会被访问并可能被染色这会导致填充多层的效果。但根据样例和题意填充是在轮廓一侧的一层空格而非多层。因此更正确的做法是只将满足条件的空格改为#但继续向四周扩展空格而不是在#上停止。但由于#不是空格不会再次被访问所以从星号出发的所有连通空格都会被检查只要它们与轮廓相邻就被染色这确实会染色所有与轮廓相邻且与星号同侧的空格可能包括多层实际上如果内部区域有多层空格最外层与轮廓相邻第二层虽然不与轮廓直接相邻但第一层被染色后变为#第二层空格与第一层#相邻但条件要求邻居是轮廓字符非空格且非#所以第二层不会被染色。因此算法结果正好是一层。实现时需注意网格宽度可能因行而异但最大宽度不超过100100100行数不超过404040。解题思路具体实现步骤如下步骤1\texttt{1}1. 读取测试用例个数casescasescases。对每个用例初始化网格数组为空格行数计数器rows0\textit{rows} 0rows0。循环读取行直到遇到以_开头的行可能包含多个下划线。将每行字符存入maze\textit{maze}maze并记录星号位置(stari,starj)(\textit{star}_i, \textit{star}_j)(stari,starj)。步骤2\texttt{2}2. 将星号位置改为空格因为星号仅用于指示起始点不参与输出。步骤3\texttt{3}3. 执行Flood Fill\texttt{Flood Fill}Flood Fill。使用递归函数floodFill(i,j)\texttt{floodFill}(i, j)floodFill(i,j)若(i,j)(i,j)(i,j)在网格范围内且未被访问且为空格则标记为已访问然后检查其上下左右四个邻居若存在邻居是轮廓字符即不是空格也不是#则将当前格子改为#。接着递归访问四个方向邻居。步骤4\texttt{4}4. 输出时对于每一行从右向左找到最后一个非空格字符的位置然后输出该行从开头到该位置的所有字符保留前导空格和中间空格。最后输出结束行即下划线行。注意轮廓字符可能是任意可打印字符除*、#、.和空格因此判断非空格且非#即为轮廓。在填充过程中#作为已填充标记不应再被当作空格处理。代码实现// Contour Painting// UVa ID: 782// Verdict: Accepted// Submission Date: 2017-10-24// UVa Run Time: 0.020s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;charmaze[40][100];introws0,visited[40][100];intoffsetx[4]{0,0,1,-1},offsety[4]{1,-1,0,0};voidfloodFill(inti,intj){if(i0irowsj0j100!visited[i][j]maze[i][j] ){visited[i][j]1;boolflagfalse;for(intk0;k4;k){intnextiioffsetx[k],nextjjoffsety[k];if(nexti0nextirowsnextj0nextj100){if(maze[nexti][nextj]! maze[nexti][nextj]!#){flagtrue;break;}}}if(flag)maze[i][j]#;for(intk0;k4;k)floodFill(ioffsetx[k],joffsety[k]);}}intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intcases;cincases;cin.ignore(1024,\n);string line;for(intc1;ccases;c){rows0;memset(maze, ,sizeof(maze));intstari,starj;while(getline(cin,line),line.front()!_){for(inti0;iline.length();i){maze[rows][i]line[i];if(line[i]*){starirows;starji;}}rows;}maze[stari][starj] ;memset(visited,0,sizeof(visited));floodFill(stari,starj);for(inti0;irows;i){for(intcolumns99;columns0;columns--){if(maze[i][columns]! ){for(intj0;jcolumns;j)coutmaze[i][j];break;}}cout\n;}coutline\n;}return0;}总结本题通过Flood Fill\texttt{Flood Fill}Flood Fill在指定侧为轮廓添加一层#填充。核心在于判断条件空格只要与轮廓字符相邻则被涂色。由于访问标记和染色同步进行确保只填充一层。输入输出格式需注意每行尾部空格的去除以及结束行下划线行的保留。该算法时间复杂度O(R×C)O(R \times C)O(R×C)空间O(R×C)O(R \times C)O(R×C)适用于网格大小有限的场景。此类问题体现了图像处理中边界填充的模拟思路。