算法1
(脉冲探测) $O(m)$
C++ 代码
#include<iostream>
#include<vector>
using namespace std;
int n,m;
int main(){
cin>>n>>m;
vector<vector<char>> b(n,vector<char>(m,'.'));
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
cin>>b[i][j];
vector<vector<char>> c;//分组放:y总的统计图思想(蓝桥杯”平均“题)
vector<char> a;//连续的B放一组:一列
for(int j=1;j<m+1;j++)
{
//前一个符合
if(b[n-1][j-1]=='B')
{
a.push_back(b[n-1][j-1]);//存好
//自己不符合或者自己的前一个已经是最后一个
if(j-1==m||b[n-1][j]!='B')
{
c.push_back(a);//放好前面连续符合的
a.clear();//重置a
}
//自己符合
//变成"下一个的前一个"放入中间容器a
}
}
cout<<c.size();
return 0;
}
算法2
(暴力枚举DFS) $O(?)$
C++ 代码
#include<iostream>
#include<vector>
using namespace std;
int n=0,m=0,cnt=0;
bool visited[100][100]={0};
//原地、右、上、左、下
int dx[]={0,-1,0,1};//行
int dy[]={1,0,-1,0};//列
void dfs(int x,int y,vector<vector<char>> b,int u){
//访问根节点
visited[x][y]=true;
//访问邻接点
for(int i=0;i<4;i++)
{
int tx=x+dx[i];
int ty=y+dy[i];
if(tx>=n||tx<0||ty>=m||ty<0||visited[tx][ty]==true||b[tx][ty]=='.')
continue;
dfs(tx,ty,b,u+1);
}
printf("这是第%d层\n",u);
}
int main(){
cin>>n>>m;
vector<vector<char>> b(n,vector<char>(m,'.'));
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
cin>>b[i][j];
for(int i=n-1;i>=0;i--)
for(int j=0;j<m;j++){
if(b[i][j]=='B'&&!visited[i][j]){//只需要从没有访问过的b开始
dfs(i,j,b,1);
cnt++;//空缺不需要,也不需要对应cnt+++
}
}
cout<<cnt;
return 0;
}