本文共 2150 字，大约阅读时间需要 7 分钟。

为了解决这个问题，我们需要计算Farmer John的田地中有多少个连通的水池。每个水池由8方向连接的水格子构成。我们可以使用广度优先搜索（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;
}
       
      
     
    
   

代码解释

通过这种方法，我们可以高效地计算出田地中连通的水池数量。

转载地址：http://iyxfk.baihongyu.com/