UVa 469 Wetlands of Florida
题目描述
题目要求计算包含指定水域单元格的湖泊面积。网格由W（水）和L（陆地）组成，相邻定义包括八个方向（上、下、左、右及四个对角线）。对于每个查询（给出水单元格的行和列坐标），输出该单元格所在连通水域的面积（即连通分量中W的数量）。
输入格式
第一行一个整数NNN，表示测试用例的数量，后面跟一个空行。每个测试用例的第一部分为网格描述：若干行，每行一个由W和L组成的字符串，表示网格的一行。网格行数nnn和列数mmm满足0<n,m≤990 < n, m \le 990<n,m≤99。网格描述后跟若干行，每行两个整数iii和jjj，表示查询的水单元格坐标（行和列，从111开始）。输入以文件结束符（EOF\texttt{EOF}EOF）终止。两个连续测试用例之间由一个空行分隔。
输出格式
对于每个查询，输出一行一个整数，表示该湖泊的面积。两个连续测试用例的输出之间由一个空行分隔。
样例
输入
1 LLLLLLLLLL LLLWLLWLL LWWLLLLLL LWWLLWWLL LLLWWLLLL LLLLLLLLL LLLWWLLWL LLLWLLLLL LLLLLLLLL 3 2 7 5输出
12 4题目分析
本题的核心是计算二维网格中八连通水域的连通分量大小。
连通性
八个方向包括：上、下、左、右、左上、右上、左下、右下。因此，洪水填充（Flood Fill\texttt{Flood Fill}Flood Fill）时需要遍历所有888个邻居。
算法
- 对于每个查询，从指定位置开始执行深度优先搜索（DFS\texttt{DFS}DFS）或广度优先搜索（BFS\texttt{BFS}BFS），统计所有可达的
W单元格数量。 - 为避免重复计数，可以将已访问的
W临时标记为其他字符（如X），统计完成后恢复（或使用单独的访问标记数组）。
注意事项
- 网格大小最大为99×9999 \times 9999×99，每次查询重新搜索完全可接受。
- 坐标从111开始，需要转换为000索引或直接在111索引数组上操作。
复杂度分析
每次查询最多访问所有单元格，时间复杂度O(n×m)O(n \times m)O(n×m)，n,m≤99n, m \le 99n,m≤99，查询次数未知但总可接受。
代码实现
// Wetlands of Florida// UVa ID: 469// Verdict: Accepted// Submission Date: 2016-07-16// UVa Run Time: 0.030s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;charmatrix[110][110];intcounter,row=0,column=0;voidrestore(){for(inti=1;i<=row;i++)for(intj=1;j<=column;j++)if(matrix[i][j]=='X')matrix[i][j]='W';}voidflood_fill(intr,intc){if(r>=1&&r<=row&&c>=1&&c<=column){if(matrix[r][c]=='W'){counter++;matrix[r][c]='X';for(inti=-1;i<=1;i++)for(intj=-1;j<=1;j++){if(i==0&&j==0)continue;flood_fill(r+i,c+j);}}}}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);string line;getline(cin,line);intcases=stoi(line);getline(cin,line);for(inti=1;i<=cases;i++){if(i>1)cout<<endl;row=0;while(getline(cin,line),line.length()>0){if(isalpha(line.front())){for(intj=0;j<line.length();j++)matrix[row+1][j+1]=line[j];row++;column=line.length();}else{istringstreamiss(line);intcell_row,cell_column;iss>>cell_row>>cell_column;counter=0;flood_fill(cell_row,cell_column);restore();cout<<counter<<'\n';}}}return0;}