算法1
(暴力枚举) $O(2^m)$
大幅剪枝,只需对最后一行dfs
C++ 代码
#include<iostream>
#include<vector>
using namespace std;
int n,m,cnt=0;;
int dy[2]={-1,1};
bool visited[110]={0};
void dfs(int y,string s,int u){
//访问根节点
visited[y]=true;
//访问邻接点
for(int i=0;i<2;i++)
{
int ty=y+dy[i];
if(ty>=m||ty<0||visited[ty]==true||s[ty]=='.')
continue;
dfs(ty,s,u+1);
}
//printf("这是第%d层\n",u);
}
int main(){
cin>>n>>m;
string s;
for(int i=0;i<n;i++)
cin>>s;//只接收最后一行
for(int j=0;j<m;j++){//(0~m-1)大幅剪枝
if(s[j]=='B'&&!visited[j]){ //从没有访问过的B开始搜索连通图
dfs(j,s,1);
cnt++; //点不需要搜,更不需要对应cnt+++
}
}
cout<<cnt;
return 0;
}