F - Oil Deposits

Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u

Description

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

 

 

解题思路：题目比较短小，容易理解。可以采用广度优先。广度优先采用的典型数据结构是优先队列。这里采用结构体记录位置。

首先从一个@出发，将此位置标记为已访问，并将所有能到达的位置标记为已访问（上下左右及对角线（8个位置），而且存在石油），并且加入队列中，当队列不为空时重复以上操作。为空后，继续枚举未访问而有石油的位置，调用BFS（）。由此可见，石油的块数即为调用BFS（）的次数。

注意：使用队列时要注意清空（这里while循环中没有其余的跳出循环语句，可以不用清空）。

        每一组数据测试之前对标记数组清零。

        memset（）--之前都是一直用memset来清空一维数组

void *memset(void *s, int ch, n);

函数解释：将s中当前位置后面的n个字节 （typedef unsigned int size_t ）用 ch 替换并返回 s 。

memset：作用是在一段内存块中填充某个给定的值，它是对较大的 或 进行清零操作的一种最快方法.

        二维数组也适用：如memset(vis,0,sizeof(vis));/memset(&vis[0][0],0,sizeof(vis))。第一个参数为要操作数据的首地址。

 

收获感想：对BFS更加理解，之前队列用得也很少，通过做题，知道队列理解也不是那么困难。

 

#include
          
           #include
           
            #include
            
             #include
             
              using namespace std;int vis[101][101],n,m;char Map[101][101];struct node{    int x,y;};queue
              
                q;bool jd(int a,int b){    if(a>=0&&a
               
                =0&&b
                
                 >n>>m) { if(n==0&&m==0) return 0; for(int i=0;i
                 
                  >Map[i][j]; memset(vis,0,sizeof(vis)); int ans=0; node tp; for(int i=0;i