学步园

题目地址

//BFS
#include <iostream>
#include<cstring>
#include<queue>
#define maxlen 110
int mat[maxlen][maxlen];
int ans;
int dir[8][2]={{0,1},{0,-1},{1,0},{1,-1},{1,1},{-1,0},{-1,1},{-1,-1}};
using namespace std;
struct node
{
    int x,y;
};
void bfs(node s,int m,int n)
{
    queue<node>q;
    node ne,ol;
    while(!q.empty())
    {
        q.pop();
    }
    mat[s.x][s.y]=1;
    q.push(s);
    while(!q.empty())
    {
        ol=q.front();
        q.pop();
        for(int l=0; l<8; l++)
        {
            ne.x=ol.x+dir[l][0];
            ne.y=ol.y+dir[l][1];
            if(ne.x>m-1||ne.y>n-1||ne.x<0||ne.y<0||mat[ne.x][ne.y]==1)continue;
            else
            {
                mat[ne.x][ne.y]=1;
                q.push(ne);
            }
        }
    }
}
int main()
{
    int m,n,i,j;
    char k;
    node s;
    memset(mat,0,sizeof(mat));
    ans=0;
    cin >> m >> n;
    for(i=0; i<m; i++)
        for(j=0; j<n; j++)
        {
            cin >>k;
            if(k=='.')mat[i][j]=1;
        }
    for(i=0; i<m; i++)
        for(j=0; j<n; j++)
        {
            if(mat[i][j]==0)
            {
                s.x=i;
                s.y=j;
                bfs(s,m,n);
                ans++;
            }
        }
    cout << ans <<  endl;
    return 0;
}