bfs练习题

蓝桥杯练习记录

1、bfs（挑战程序设计竞赛）P32

代码如下：

#include<cstdio>#include<queue>#define maxn 105using namespace std;char field[maxn][maxn];typedef pair<int,int>P;int N,M;int dis[10][3]= { {0,1},{0,-1},{-1,0},{1,0},{-1,-1},{-1,1},{1,-1},{1,1} };void bfs(int x,int y){    queue<P>que;    que.push(P(x,y));    field[x][y]='.';    while(que.size())    {        P p=que.front();        que.pop();        for(int i=0; i<8; i++)        {                int nx=p.first+dis[i][0];                int ny=p.second+dis[i][1];                if(nx>0&&nx<=N&&ny>0&ny<=M&&field[nx][ny]=='W')                {                    que.push(P(nx,ny));                    field[nx][ny]='.';                }            }    }    return ;}int main(){    int counter;    while(~scanf("%d %d",&N,&M))    {        getchar();  ///很重要        counter=0;///注意初始化的位置        for(int i=1; i<=N; i++)        {            for(int j=1; j<=M; j++)            {                scanf("%c",&field[i][j]);            }  ///注意大括号            getchar();///很重要        }        for(int i=1; i<=N; i++)            for(int j=1; j<=M; j++)                if(field[i][j]=='W')                {                    bfs(i,j);                    counter++;                }        PRintf("%d/n",counter);    }    return 0;}