题解 P6438 【[COCI2011-2012#6] PROZORI】

· · 题解

此题用搜索简单水过

思路：用广搜，先遍历整栋楼的的 map，如果不是窗户的边框 '#'，则BFS搜索出这是哪一种窗户，再给已经搜过的用 f_i,_j 标记，最后输出即可。

Code: 
#include<bits/stdc++.h> //c++专属万能头
using namespace std;
const int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1}; //可以走的4个方向
int num,n,m,a[6]; //a表示第i种窗户的个数，num表示在bfs函数结束后整个窗户的*的个数
char ch[502][502];
bool f[502][502]; //最多可以达到5n+1*5m+1,也就是5*100+1=501，故定义到502
struct node
{
    int x,y;
}; //定义一个结构体
void bfs(int sx,int sy) //bfs函数
{
    queue<node>que; //node类型的队列
    num=0; //num清零
    node temp;
    temp.x=sx;temp.y=sy;
    que.push(temp); //第一个入列
    f[sx][sy]=true; //这一点很容易遗漏，要把第一个点清为不可走
    if (ch[sx][sy]=='*') ++num; //记得判断第一个点是否是*号
    while (!que.empty()) //循环开始
    {
        node a=que.front();
        for (int i=0;i<4;++i) //逐个搜索每个方向
        {
            int nx=a.x+dx[i],ny=a.y+dy[i];
            if (nx>=1&&nx<=n&&ny>=1&&ny<=m&&ch[nx][ny]!='#'&&!f[nx][ny]) //满足条件
            {
                node t;
                t.x=nx;t.y=ny;
                que.push(t); //入列
                if (ch[nx][ny]=='*') ++num; //判断
                f[nx][ny]=true; //清为不可走
            }
        }
        que.pop(); //出列
    }
}
int main()
{
    cin>>n>>m;
    n=5*n+1;m=5*m+1; //把n,m更新
    for (int i=1;i<=n;++i)
        for (int j=1;j<=m;++j)
            cin>>ch[i][j];
    memset(a,0,sizeof(a)); //a数组清零
    for (int i=1;i<=n;++i)
        for (int j=1;j<=m;++j)
            if (ch[i][j]!='#'&&!f[i][j])
            {
                bfs(i,j);++a[num/4+1]; //num/4+1就是bfs中窗户状态，不信可以去试
            }
    for (int i=1;i<=5;++i) cout<<a[i]<<' '; //输出
    return 0; //完美的结束
}