用C++代码实现:由于最近下雨,水汇集在农夫约翰田园各处,田园是一个N×M个方格表示(1 ≤n ≤100;1≤M≤100)的矩形。每一方格要么是水('W”)(大写),要么是干燥的土地(“.”)。农民约翰想找出他的田园有多少个水坑。水坑的定义是:W通过八个方向连接成的一片算作是一个水坑。 给定一个田园矩阵,即农夫约翰的田园,确定他的田园里有多少个水坑。 输入 输入的第一行是一个整数,即n和m 接下来有n行,每行有m个字符('W' 或者 '.') 输出 输出有多少个水坑
时间: 2024-02-13 20:05:25 浏览: 74
以下是C++代码实现:
```c++
#include<iostream>
#include<cstring>
using namespace std;
const int MAXN = 105;
char field[MAXN][MAXN];
bool visited[MAXN][MAXN];
int n, m;
void dfs(int x, int y) {
visited[x][y] = true;
for(int dx=-1; dx<=1; dx++) {
for(int dy=-1; dy<=1; dy++) {
int nx = x + dx, ny = y + dy;
if(nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny] && field[nx][ny] == 'W')
dfs(nx, ny);
}
}
}
int countPonds() {
memset(visited, false, sizeof(visited));
int cnt = 0;
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
if(!visited[i][j] && field[i][j] == 'W') {
cnt++;
dfs(i, j);
}
}
}
return cnt;
}
int main() {
cin >> n >> m;
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
cin >> field[i][j];
}
}
cout << countPonds() << endl;
return 0;
}
```
在这个代码中,我们使用了深度优先搜索(DFS)来实现对水坑的搜索。我们从田园的每一个方格开始,如果该方格是水('W'),且还没有被访问过,就从该方格开始进行DFS搜索,并标记所有搜索到的方格。这样,我们就可以找出所有的水坑数量。
代码中的countPonds()函数就是实现了这个搜索算法,并返回水坑的数量。我们在主函数中,读入田园的字符矩阵,并输出搜索结果。
注意:这个算法中使用的DFS搜索是一个比较经典的算法,但是在实际应用中,可能会出现一些问题,例如:算法复杂度过高,无法处理超大规模的数据;或者算法无法处理某些特殊情况(例如:存在大规模的“孔洞”导致搜索无法进行)。这时候,我们需要考虑其他的搜索算法或者优化方法来解决这些问题。
阅读全文