文章
21
粉丝
0
获赞
19
访问
3.6k
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int n, m;
vector<string> map;
// 方向矩阵
int dir[2][8] = {{0, 0, 1, 1, 1, -1, -1, -1},
{1, -1, 0, 1, -1, 0, 1, -1}};
// 每次找到一点后向周围蔓延
void dfs(int i, int j){
// 越界和非水坑就返回
if(i < 0 || i >= n || j < 0 || j >= m || map[i][j] != 'W')
return;
map[i][j] = '.'; // 把水坑填上防止二次遍历
for(int k = 0; k < 8; k++)
dfs(i + dir[0][k], j + dir[1][k]);
}
int main(){
cin >> n >> m;
map.resize(n, string(m, '.'));
for(int i = 0; i < n; i++)
cin >> map[i];
//------------------------------------
int ans = 0;
// 遍历找水坑
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(map[i][j] == 'W'){
dfs(i, j);
ans++; // 每次进入dfs必定将一个相连通的水坑填上,因此进入次数就是答案数
}
}
}
cout << ans << endl;
return 0;
}
登录后发布评论
暂无评论,来抢沙发