tips:
1.统计进行了几次bfs,判断队首结点的相邻结点是否符合入队条件单独写成一个judge函数
2.使用memset函数要包含<cstring>
#include<cstdio> #include<queue> #include<algorithm> #include<cstring> using namespace std; const int M=105; struct node{ int x;int y; }Node; int matrix[M][M]; bool inq[M][M]; int n,m; int x[8]={-1,-1,-1,0,0,1,1,1}; int y[8]={1,0,-1,1,-1,1,0,-1}; bool judge(int x,int y){ if(x<0 || x>=n || y<0 || y>=m ) return false; if(matrix[x][y] == ‘.‘ || inq[x][y]== 1) return false; return true; } void BFS(int a,int b){ queue<node> Q; Node.x=a,Node.y=b; Q.push(Node); inq[a][b]=1; while(!Q.empty()){ node top=Q.front(); Q.pop(); for(int i=0;i<8;i++){ int dx=top.x+x[i]; int dy=top.y+y[i]; if(judge(dx,dy)){ Node.x=dx,Node.y=dy; Q.push(Node); inq[dx][dy]=1; } } } } int main(){ while(scanf("%d%d",&n,&m)!=EOF){ getchar(); for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ scanf("%c",&matrix[i][j]); } getchar(); } memset(inq,0,sizeof(inq)); int ans=0; for(int i=0;i<n;i++){ for(int j=0; j<m;j++){ if(matrix[i][j]== ‘W‘ && inq[i][j]==0){ ans++; BFS(i,j); } } } printf("%d\n",ans); } return 0; }
原文:https://www.cnblogs.com/SUMaywlx/p/9495321.html