首页 > 代码库 > HDU 1241 <Oil Deposits> <搜索>

HDU 1241 <Oil Deposits> <搜索>

2024-08-11 08:34:23   217人阅读

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
 
 
 
题意：一个油田和9格内油田联通。问总共有多少块不联通的油田。
题解：搜索。
#include<stdio.h>  #include<string.h>  #include<queue>using namespace std;int map[200][200];queue<int>x, y;int m, n,k;int judge(int x, int y){    if (x >= 1 && y >= 1 && x <= m&&y <= n&&map[x][y] == 0)return 1;    return 0;}void re(int x, int y, int k){    //printf("%d\n", k);    map[x][y] = k;    for (int i = -1;i <= 1;i++)        for (int j = -1;j <= 1;j++)            if (judge(x + i, y + j))re(x + i, y + j, k);}int main(){    char s;    while (scanf("%d%d", &m, &n) != EOF && m!=0)    {        k = 0;        memset(map, 0, sizeof(map));        for (int i = 1;i <= m;i++)         {            //getchar();            for (int j = 1;j <= n;j++)            {                //s = getchar();                scanf(" %c", &s);                if (s == ‘*‘)map[i][j] = -1;            }        }    //    for (int i = 1;i <= m;i++)    //    {    //        for (int j = 1;j <= n;j++)    //            printf("%d", map[i][j]);    //        printf("\n");    //    }        for (int i = 1;i <= m;i++)            for (int j = 1;j <= n;j++)                if (map[i][j] == 0)re(i, j, ++k);        printf("%d\n", k);    }}

 

HDU 1241 <Oil Deposits> <搜索>


联系
我们