看别的神犇用的都是并查集,我还是用暴搜吧(doge
下面纯暴搜
#include <bits/stdc++.h>
using namespace std;
int n, m, ans; // N行M列和答案
char c[105][105]; // 存储农田的二维向量
void dfs(int x, int y) { //暴搜
if(c[x][y + 1] == 'W'){
c[x][y + 1]='.'; //将水坑改为陆地
dfs(x, y + 1);
}
if(c[x][y - 1] == 'W'){
c[x][y - 1] = '.'; //同上
dfs(x, y - 1);
}
if(c[x + 1][y] == 'W'){
c[x + 1][y] = '.'; //同上
dfs(x + 1, y);
}
if(c[x - 1][y] == 'W'){
c[x - 1][y] = '.'; //同上
dfs(x - 1, y);
}
if(c[x + 1][y + 1] == 'W'){
c[x + 1][y + 1] = '.'; //同上
dfs(x + 1, y + 1);
}
if(c[x + 1][y - 1] == 'W'){
c[x + 1][y - 1] = '.'; //同上
dfs(x + 1, y - 1);
}
if(c[x - 1][y + 1]=='W'){
c[x - 1][y + 1] = '.'; //同上
dfs(x - 1, y + 1);
}
if(c[x - 1][y - 1] == 'W'){
c[x - 1][y - 1] = '.'; //同上
dfs(x - 1, y - 1);
}
}
int main(){
cin >> n >> m; // 输入农田的行数和列数
// 读入农田数据
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++) cin >> c[i][j];
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(c[i][j] == 'W'){
c[i][j] = '.', ans++; //将水坑改为陆地
dfs(i, j); // 对每个未访问的水格子进行DFS
}
}
}
cout << ans;// 输出水坑的数量
return 0;
}
标签:P1596,洛谷,int,题解,Lake,dfs
From: https://www.cnblogs.com/wayneoi/p/18307302