F - Oil Deposits HDU - 1241

2-Day1-F
The GeoSurvComp geologic survey company is responsible for detecting underground oil deposits. GeoSurvComp works with one large rectangular region of land at a time, and creates a grid that divides the land into numerous square plots. It then analyzes each plot separately, using sensing equipment to determine whether or not the plot contains oil. A plot containing oil is called a pocket. If two pockets are adjacent, then they are part of the same oil deposit. Oil deposits can be quite large and may contain numerous pockets. Your job is to determine how many different oil deposits are contained in a grid.
Input
The input file contains one or more grids. Each grid begins with a line containing m and n, the number of rows and columns in the grid, separated by a single space. If m = 0 it signals the end of the input; otherwise 1 <= m <= 100 and 1 <= n <= 100. Following this are m lines of n characters each (not counting the end-of-line characters). Each character corresponds to one plot, and is either *', representing the absence of oil, or@', representing an oil pocket.
Output
For each grid, output the number of distinct oil deposits. Two different pockets are part of the same oil deposit if they are adjacent horizontally, vertically, or diagonally. An oil deposit will not contain more than 100 pockets.
Sample Input
1 1
*
3 5
@@*
@
@@*
1 8
@@*@
5 5
**
@
@@@
@**@
@@@
@
@@**@
0 0
Sample Output
0
1
2
2
题意:水题,有几块油田?
思路:深搜即可
代码如下:

#include<bits/stdc++.h>
using namespace std;

#define N 200
int m,n,v[N][N],ans;
char np[N][N];
int a[8]={-1,-1,0,1,1,1,0,-1};
int b[8]={0,1,1,1,0,-1,-1,-1};

void dfs(int x,int y)
{
    int nx,ny;
    v[x][y]=1;
    for(int i=0;i<8;i++){
        nx=x+a[i];
        ny=y+b[i];
        if(nx>0&&nx<=m&&ny>0&&ny<=n&&v[nx][ny]==0&&np[nx][ny]=='@')
        {
            dfs(nx,ny);
            np[x][y]='*';
        }
    }
}
int main()
{
    while(scanf("%d%d",&m,&n)!=EOF){
        if(m==0&&n==0)
        break;
        memset(np,0,sizeof(np));
        memset(v,0,sizeof(v));
        ans=0;
        for(int i=1;i<=m;i++){
            scanf("%s",np[i]+1);
        }
        for(int x=1;x<=m;x++){
            for(int y=1;y<=n;y++){
                if(np[x][y]=='@'&&v[x][y]==0){
                    dfs(x,y);
                    ans++;
                }
            }
        }printf("%d\n",ans);
    }
    return 0;
}
全部评论

相关推荐

Z_eus:别打招呼直接发你的优势
点赞 评论 收藏
分享
叶扰云倾:进度更新,现在阿里云面完3面了,感觉3面答得还行,基本都答上了,自己熟悉的地方也说的比较细致,但感觉面试官有点心不在焉不知道是不是不想要我了,求阿里收留,我直接秒到岗当阿里孝子,学校那边的房子都退租了,下学期都不回学校,全职猛猛实习半年。这种条件还不诱人吗难道 然后现在约到了字节的一面和淘天的复活赛,外加猿辅导。华为笔试完没动静。 美团那边之前投了个base广州的,把我流程卡麻了,应该是不怎么招人,我直接简历挂了,现在进了一个正常的后端流程,还在筛选,不知道还有没有hc。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务