UVa 722 Lakes

题目描述给定一个由0水和1陆地组成的矩形网格网格大小不超过99×9999 \times 9999×99。网格外围被陆地1包围。给定一个水域单元格的位置行、列要求计算与该水域单元格水平或垂直相连通的整个水域区域所包含的单元格总数。输入格式第一行包含一个整数MMM表示数据组数。随后有一个空行接着是MMM组数据每组数据之间有一个空行。每组数据第一行包含两个字符串分别表示行号和列号每个字符串由数字字符组成可能包含前导零。第二行开始是网格的每一行每行是一个长度不超过999999的010101字符串直到遇到空行或文件结束。输出格式对于每组数据输出一行包含一个整数即该水域区域的面积。每组输出之间用一个空行分隔。样例输入1 02 01 1001101 0011111 0001001 1100011 1111111 1100110 1110111样例输出12题目分析给定一个010101矩阵其中0表示水1表示陆地。要求从指定位置出发统计所有通过上下左右四个方向连通的0的个数即四连通水域的面积。这是一个典型的连通块大小统计问题可以使用深度优先搜索DFS\texttt{DFS}DFS或广度优先搜索BFS\texttt{BFS}BFS解决。由于网格最大99×9999 \times 9999×99递归深度不超过992980199^2 98019929801用递归DFS\texttt{DFS}DFS安全。解题思路采用递归Flood fill\texttt{Flood fill}Flood fill也称种子填充算法。从给定的起始单元格(r,c)(r, c)(r,c)开始若该单元格在网格内且为0则面积计数加111将该单元格标记为已访问改为1然后递归访问其上下左右四个相邻单元格。最终计数即为该水域区域面积。注意输入格式起始坐标以字符串形式给出可能带有前导零需转换为整数每组数据间有空行网格行可能被空行分隔。读取时需先读入起始坐标字符串并转换为整数然后循环读取网格行直到遇到空行或文件结束将每行存入数组。由于网格外围被陆地包围无需额外边界判断但递归函数仍需检查边界。代码实现// Lakes// UVa ID: 722// Verdict: Accepted// Submission Date: 2017-03-02// UVa Run Time: 0.000s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intwater0,r0,c0,rt0,ct0;;chargrid[110][110];voidflood_fill(intr,intc){if(r0rrtc0cctgrid[r][c]0){water;grid[r][c]1;flood_fill(r-1,c);flood_fill(r1,c);flood_fill(r,c-1);flood_fill(r,c1);}}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intcases0;string row,column,line;cincases;for(intk1;kcases;k){cinrowcolumn;rstoi(row),cstoi(column);cin.ignore(1024,\n);rt0;memset(grid,0,sizeof(grid));while(getline(cin,line),line.length()0){for(inti0;iline.length();i)grid[rt][i]line[i];rt,ctline.length();}water0;flood_fill(r-1,c-1);if(k1)cout\n;coutwater\n;}return0;}总结本题是经典的连通块统计问题使用Flood fill\texttt{Flood fill}Flood fill算法即可高效求解。注意输入格式的特殊性字符串坐标、空行分隔需正确处理。标记访问可通过将0改为1避免重复计数同时无需额外访问数组。递归深度在99×9999 \times 9999×99范围内安全。该解法时间复杂度O(R×C)O(R \times C)O(R×C)空间复杂度O(R×C)O(R \times C)O(R×C)满足题目限制。