题目描述题目要求计算包含指定水域单元格的湖泊面积。网格由W水和L陆地组成相邻定义包括八个方向上、下、左、右及四个对角线。对于每个查询给出水单元格的行和列坐标输出该单元格所在连通水域的面积即连通分量中W的数量。输入格式第一行一个整数NNN表示测试用例的数量后面跟一个空行。每个测试用例的第一部分为网格描述若干行每行一个由W和L组成的字符串表示网格的一行。网格行数nnn和列数mmm满足0n,m≤990 n, m \le 990n,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//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;charmatrix[110][110];intcounter,row0,column0;voidrestore(){for(inti1;irow;i)for(intj1;jcolumn;j)if(matrix[i][j]X)matrix[i][j]W;}voidflood_fill(intr,intc){if(r1rrowc1ccolumn){if(matrix[r][c]W){counter;matrix[r][c]X;for(inti-1;i1;i)for(intj-1;j1;j){if(i0j0)continue;flood_fill(ri,cj);}}}}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);string line;getline(cin,line);intcasesstoi(line);getline(cin,line);for(inti1;icases;i){if(i1)coutendl;row0;while(getline(cin,line),line.length()0){if(isalpha(line.front())){for(intj0;jline.length();j)matrix[row1][j1]line[j];row;columnline.length();}else{istringstreamiss(line);intcell_row,cell_column;isscell_rowcell_column;counter0;flood_fill(cell_row,cell_column);restore();coutcounter\n;}}}return0;}