题目描述
迷宫由矩形房间组成，在二维网格上表示，网格点由字符标记。房间墙壁由同一字符（任意非*、非空格的字符）标记，房间内部为空格。所有房间大小相同，墙壁宽度为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为空格，行数计数器r=0r = 0r=0。使用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≤30，C≤80C \le 80C≤80，效率极高。
代码实现
// Maze Exploration// UVa ID: 784// Verdict: Accepted// Submission Date: 2016-11-29// UVa Run Time: 0.010s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;charmaze[35][85];intoffset[4][2]={{-1,0},{1,0},{0,-1},{0,1}};voidflood_fill(inti,intj,charold,chartarget){if(i>=0&&i<35&&j>=0&&j<85&&maze[i][j]==old){maze[i][j]=target;for(intk=0;k<4;k++)flood_fill(i+offset[k][0],j+offset[k][1],old,target);}}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intcases=0;cin>>cases;cin.ignore(1024,'\n');for(intc=1;c<=cases;c++){memset(maze,' ',sizeof(maze));string line;intr=0,x=0,y=0;while(getline(cin,line),line.front()!='_'){inti=0;for(;i<line.length();i++){maze[r][i]=line[i];if(line[i]=='*'){x=r,y=i;}}maze[r][i]='\n';r++;}maze[x][y]=' ';flood_fill(x,y,' ','#');for(inti=0;i<r;i++)for(intj=0;j<80;j++){cout<<maze[i][j];if(maze[i][j]=='\n')break;}cout<<line<<'\n';}return0;}总结
本题通过Flood Fill\texttt{Flood Fill}Flood Fill将迷宫中的连通区域涂色，关键在于识别门也是空格，因此涂色操作与普通空格无异。输入处理需保留各行末尾空格，输出时按原行长度输出，不能统一截断。该解法简单直接，利用了Flood Fill\texttt{Flood Fill}Flood Fill在网格连通性处理中的经典作用。注意数组大小要足够容纳最多303030行、每行808080个字符，并留有余量。分隔行的保留和输出确保了格式与输入一致。
