题意分析

给定一个 (N × M) 的方格矩阵表示农夫约翰的田地，矩阵中的 'W' 表示积水，'.' 表示旱地。若若干个 'W' 方格相连（包括八个方向相邻），则它们构成一个池塘。需要计算矩阵中池塘的数量。

解题思路

使用深度优先搜索（DFS）来遍历矩阵。每当遇到一个 'W' 方格时，就从该方格开始进行 DFS，将与该方格相连的所有 'W' 方格标记为 '.'，表示这些方格已被访问过，这样就找到了一个池塘。重复这个过程，直到遍历完整个矩阵，记录找到的池塘数量。

分析

1.本题可以将矩阵看作一个图，每个方格是图中的一个节点，相邻的方格之间有边相连。问题就转化为求图中连通分量的数量。

2.DFS 是一种适合解决连通分量问题的算法，它可以递归地访问与起始节点相连的所有节点。

实现步骤

1.读取输入的 N 和 M，以及矩阵的每个方格字符。

2.遍历矩阵，当遇到 'W' 方格时，调用 DFS 函数。

3.在 DFS 函数中，将当前 'W' 方格标记为 '.'，并递归地访问其八个相邻方格中为 'W' 的方格。

4.每完成一次 DFS，池塘数量加 1。

5.输出池塘的总数。

代码实现

#include<stdio.h>
#include<iostream>
using namespace std;

const int N_Max=100,M_Max=100;
char Lake[N_Max][M_Max];
int N,M;

void dfs(int n,int m)
{
    if(Lake[n][m]=='.')
        return;
    Lake[n][m]='.';
    for(int i=-1;i!=2;i++)
        for(int j=-1;j!=2;j++){
            if( 0<=n+i&&n+i<N && 0<=m+j&&m+j<M && Lake[n+i][m+j]=='W')
                dfs(n+i,m+j);
        }
    
    return ;
}

int main()
{
    cin>>N>>M;
    for(int i=0;i!=N;i++)
        for(int j=0;j!=M;j++)
        {
            cin>>Lake[i][j];
        }
    int res=0;
    for(int i=0;i!=N;i++)
        for(int j=0;j!=M;j++){
            if(Lake[i][j]=='W'){
                dfs(i,j);
                res++;
            }
        }
    printf("%d\n",res);
    return 0;
}

代码说明：

1.Lake 数组用于存储矩阵信息。

2.dfs 函数实现了深度优先搜索，将当前 'W' 方格标记为 '.'，并递归访问其相邻的 'W' 方格。

3.在 main 函数中，读取输入，遍历矩阵，遇到 'W' 方格时调用 dfs 函数，并记录池塘数量，最后输出结果。