UVa 784 Maze Exploration

题目描述迷宫由矩形房间组成在二维网格上表示网格点由字符标记。房间墙壁由同一字符任意非*、非空格的字符标记房间内部为空格。所有房间大小相同墙壁宽度为333点厚度为111点相邻房间共享整面墙。房间之间通过门连通门位于墙壁正中央无通向外部的门。给定一个标有星号*的起始房间星号位于房间中央要求将与起始房间通过门连通的所有房间内部包括门全部涂成#。输出涂色后的迷宫格式与原输入一致包括分隔行。输入格式第一行为一个正整数NNN表示迷宫个数。随后NNN个迷宫每个迷宫由若干行组成行长度不定最长不超过808080个字符。每个迷宫以一行全部由下划线_组成的行结束。迷宫行数最多303030行每行最多808080个字符。输出格式对于每个迷宫输出涂色后的完整迷宫包括分隔行下划线行格式与原输入相同。样例输入2 XXXXXXXXX X X X X * X X X X XXXXXXXXX __________ XXXXXXXXX X X X X X X X X X XXXXXXXXX __________样例输出XXXXXXXXX X###X###X X###X###X X###X###X XXXXXXXXX __________ XXXXXXXXX X X X X X X X X X XXXXXXXXX __________题目分析迷宫的房间内部由空格组成墙壁由非空格字符如X组成。门位于墙壁中间在网格中体现为墙壁上的一个空格即门的字符也是空格。起始房间由星号标记星号位于房间内部的空格位置。涂色操作要求将与起始房间通过门连通的整个房间内部空格全部变为#包括门。由于房间内部是连通的且门也是空格因此只需从星号位置开始进行四方向Flood Fill\texttt{Flood Fill}Flood Fill将所有连通的空格替换为#即可。墙壁和其他字符保持不变。最后输出时需保留每行末尾的空格以及分隔行。解题思路实现步骤如下步骤1\texttt{1}1. 读取测试用例个数casescasescases。对每个用例初始化字符数组maze\textit{maze}maze为空格行数计数器r0r 0r0。使用getline\texttt{getline}getline逐行读取直到遇到以_开头的行分隔行。将每行字符复制到maze\textit{maze}maze的对应行中并记录星号所在位置(stari,starj)(\textit{star}_i, \textit{star}_j)(stari​,starj​)。每行末尾可能包含空格但getline\texttt{getline}getline会保留它们。步骤2\texttt{2}2. 将星号位置改为空格因为星号仅表示起点涂色后应变为#的一部分。然后从星号位置开始调用Flood Fill\texttt{Flood Fill}Flood Fill函数将所有四方向连通的空格替换为#。步骤3\texttt{3}3. 输出迷宫。对于每一行从000到797979依次输出字符若遇到换行符\n或读取到行末则停止。由于输入行可能少于808080个字符数组中的其他位置为初始空格但不属于该行实际内容因此需按实际输入行长度输出。代码通过检查maze[i][j] \n来确定行结束这是因为在读取时手动在每行末尾添加了换行符。最终输出分隔行下划线行。该算法时间复杂度O(R×C)O(R \times C)O(R×C)空间复杂度O(R×C)O(R \times C)O(R×C)其中R≤30R \le 30R≤30C≤80C \le 80C≤80效率极高。代码实现// Maze Exploration// UVa ID: 784// Verdict: Accepted// Submission Date: 2016-11-29// UVa Run Time: 0.010s//// 版权所有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,chartarget){if(i0i35j0j85maze[i][j]old){maze[i][j]target;for(intk0;k4;k)flood_fill(ioffset[k][0],joffset[k][1],old,target);}}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intcases0;cincases;cin.ignore(1024,\n);for(intc1;ccases;c){memset(maze, ,sizeof(maze));string line;intr0,x0,y0;while(getline(cin,line),line.front()!_){inti0;for(;iline.length();i){maze[r][i]line[i];if(line[i]*){xr,yi;}}maze[r][i]\n;r;}maze[x][y] ;flood_fill(x,y, ,#);for(inti0;ir;i)for(intj0;j80;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在网格连通性处理中的经典作用。注意数组大小要足够容纳最多303030行、每行808080个字符并留有余量。分隔行的保留和输出确保了格式与输入一致。