问题描述

GeoSurvComp地质调查公司负责探测地下石油储藏。 GeoSurvComp现在在一块矩形区域探测石油，并把这个大区域分成了很多小块。他们通过专业设备，来分析每个小块中是否蕴藏石油。如果这些蕴藏石油的小方格相邻，那么他们被认为是同一油藏的一部分。在这块矩形区域，可能有很多油藏。你的任务是确定有多少不同的油藏

Input

输入可能有多个矩形区域（即可能有多组测试）。每个矩形区域的起始行包含m和n，表示行和列的数量，1<=n,m<=100，如果m =0表示输入的结束，接下来是n行，每行m个字符。每个字符对应一个小方格，并且要么是’*’，代表没有油，要么是’@’，表示有油

Output

对于每一个矩形区域，输出油藏的数量。两个小方格是相邻的，当且仅当他们水平或者垂直或者对角线相邻（即8个方向）

Sample Input

1 1
*
3 5
*@*@*
**@**
*@*@*
1 8
@@****@*
5 5
****@
*@@*@
*@**@
@@@*@
@@**@
0 0

Sample Output

0
1
2
2

思路

遍历每个点, 遇到一个@, 执行一次广搜函数把相连的全部标记

AC代码

#include<cstdio>
#include<queue>
using namespace std;

struct zuobiao{
    int m;
    int n;
};
char a[101][101];
int m, n;
int fangxiang[8][2] = { {-1,-1},{-1,0},{-1,1},{0,-1},
                        {0,1},{1,-1},{1,0},{1,1} };

void bfs(int _m, int _n)
{
    queue <zuobiao> q;
    zuobiao xxx;
    xxx.m = _m; xxx.n = _n;
    q.push(xxx);

    while (!q.empty())
    {
        zuobiao _x = q.front();
        a[_x.m][_x.n] = '0';
        q.pop();
        for (int i = 0; i < 8; i++)
        {
            _x.m += fangxiang[i][0];
            _x.n += fangxiang[i][1];
            if (a[_x.m][_x.n] == '@')
                q.push(_x);
        }
    }
}

int main()
{
    while (true)
    {
        int num = 0;
        scanf("%d%d", &m, &n);
        if (m == 0) break;

        for (int i = 0; i < m; i++)
            scanf("%s", a[i]);
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (a[i][j] == '@')
                {
                    num++;
                    bfs(i, j);
                }
        printf("%d\n", num);
    }
    return 0;
}