解决PoJ 2386：湖的数量计算

"这篇资源是关于ACM竞赛中的一个编程问题——‘Lake Counting’，即计算农民John的田地里积水区域（湖泊）的数量。题目描述了一个 NxM 的矩形田地，其中 'W' 表示水，'.' 表示没有水。任务是根据输入的田地布局确定湖泊的总数。提供的参考答案使用了广度优先搜索（BFS）算法来解决此问题。" 在编程竞赛，特别是ACM（国际大学生程序设计竞赛）中，经常遇到各种算法问题，如图论、动态规划、搜索算法等。这个问题属于图论中的连通分量计算，具体是通过模拟水的流动来确定“湖泊”（被水包围的区域）。下面将详细讲解如何解决这个问题。 首先，我们要理解输入描述：第一行包含两个整数N和M，分别表示田地的行数和列数。接下来的N行中，每行包含M个字符，'W'表示有水，'.'表示无水。我们的目标是找出所有相互连接的'W'形成的湖泊，并计算它们的个数。 参考答案中，定义了一个Node结构体来存储坐标，以及一个二维数组map来存储田地状态。dir数组用来表示8个可能的移动方向，这在广度优先搜索中常用。变量num用于记录湖泊数量，n和m分别是田地的行数和列数。 BFS（广度优先搜索）是一种用于遍历或搜索树或图的算法。在这个问题中，我们从每个'W'开始进行搜索，如果相邻的格子也是'W'，则继续搜索，直到所有的相邻'W'都被访问过。在搜索过程中，我们将已访问过的格子标记，以避免重复计数。当队列为空时，表示所有与起点相连的'W'都已经处理完毕，这时如果发现一个新的'W'，说明我们找到了一个新的湖泊。 具体步骤如下： 1. 初始化num为0，用于记录湖泊数量。 2. 遍历田地中的每一个位置，如果当前位置是'W'且未被访问过，执行BFS搜索。 3. BFS函数中，使用队列进行广度优先搜索，每次取出队列头部的节点，检查其周围8个方向的邻居。 4. 如果邻居在田地范围内，是'W'且未被访问过，将其加入队列并标记为已访问。 5. 当队列为空时，说明当前湖泊的所有'W'已经处理完毕，num加1，表示找到一个新的湖泊。 6. 继续遍历田地，直到所有'W'都检查完。 7. 最后输出num，即湖泊的总数。 这个算法的时间复杂度是O(N * M)，因为每个格子最多只会被访问一次。空间复杂度取决于田地的大小，最坏情况下需要存储所有'W'的位置，因此是O(N * M)。 解决这类问题的关键在于理解如何利用搜索算法（如BFS）来寻找和计数连通的组件，以及有效地处理二维数组来模拟实际场景。在ACM竞赛中，熟悉并熟练掌握这些基础算法是非常重要的。