本文共 2101 字，大约阅读时间需要 7 分钟。
为了解决这个问题，我们需要计算Farmer John的田地中有多少个连通的水池。每个水池由8方向连接的水格子构成。我们可以使用广度优先搜索（BFS）来解决这个问题。
方法思路
读取输入：首先读取田地的行数N和列数M，然后读取田地的网格数据。 初始化数据结构：创建一个二维数组来记录哪些格子已经被访问过。 搜索算法：遍历每一个格子，如果发现一个未被访问过的水格子，就开始一次BFS，标记所有与之连通的水格子为已访问。 计数结果：每次完成一次BFS后，计数器加一，最后输出计数器的值。 解决代码
#include #include #include using namespace std;int main() { int n, m; cin >> n >> m; char grid[n][m]; for (int i = 0; i < n; ++i) { string s; cin >> s; for (int j = 0; j < m; ++j) { grid[i][j] = s[j]; } } bool visited[n][m]; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { visited[i][j] = false; } } int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1}; int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1}; int ans = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (!visited[i][j] && grid[i][j] == 'W') { queue > q; q.push({i, j}); visited[i][j] = true; while (!q.empty()) { auto current = q.front(); q.pop(); int x = current.first; int y = current.second; for (int k = 0; k < 8; ++k) { int newx = x + dx[k]; int newy = y + dy[k]; if (newx >= 0 && newx < n && newy >= 0 && newy < m) { if (!visited[newx][newy] && grid[newx][newy] == 'W') { visited[newx][newy] = true; q.push({newx, newy}); } } } } ans++; } } } cout << ans << endl; return 0;}
代码解释
读取输入：首先读取N和M，然后读取每行的数据并存储到二维数组grid中。 初始化访问数组：创建一个二维数组visited来记录每个格子是否被访问过。 定义方向数组：dx和dy数组分别表示格子在行和列方向上的变化，用于处理8方向的邻居。 遍历每个格子：如果当前格子是水且未被访问过，就开始一次BFS。 BFS处理：从当前格子开始，使用队列处理所有连通的水格子，标记为已访问。 计数连通水池：每次完成一次BFS后，计数器加一，最后输出计数器的值。 通过这种方法，我们可以高效地计算出田地中连通的水池数量。
转载地址：http://iyxfk.baihongyu.com/