背景:主要是熟悉bfs写法,虽然1Y,但是中间调试了几次,还是有小失误。看了@liujc的写法,dfs也可,但是感觉bfs效率高些?
我的代码:
#include<cstdio> #include<iostream> #include<cstring> #include<queue> using namespace std; char diagram[109][109]; struct place{int x,y;}temp1,temp2; int dir[8][2]={1,0,-1,0,0,1,0,-1,1,1,1,-1,-1,1,-1,-1},n,m; void pond(int i,int j){ diagram[i][j]='.'; temp1.x=i; temp1.y=j; queue<place> q; q.push(temp1); while(!q.empty()){ temp1=q.front(); for(int k=0;k < 8;k++){ temp2.x=temp1.x+dir[k][0]; temp2.y=temp1.y+dir[k][1]; if(diagram[temp2.x][temp2.y] == 'W'){ diagram[temp2.x][temp2.y]='.'; q.push(temp2); } } q.pop(); } } int main(void){ while(~scanf("%d%d",&n,&m)){ getchar(); memset(diagram,'.',sizeof(diagram)); for(int i=1;i <= n;i++){ for(int j=1;j <= m;j++) scanf("%c",&diagram[i][j]); getchar(); } int count=0; for(int i=1;i <= n;i++){ for(int j=1;j <= m;j++){ if(diagram[i][j] == 'W'){ pond(i,j); count++; } } } printf("%d\n",count); } return 0; }