uva 572 - Oil Deposits

题目链接

题目大意：给一个由‘*’和‘@’组成的图（100*100），求由‘@’连通的图有几个

解题思路：用一个二维字符数组将图存起来，用dfs遍历图（8个方向）如果未访问过且为‘@’则标记

注意事项：访问数组要清零

#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char p[105][105];
int m,n;
int v[105][105];
int a[][2]={
             {-1,-1},{0,-1},{1,-1},
             {-1,0},         {1,0},
             {-1,1},   {0,1},{1,1}
           };

void dfs(int h,int l)
{
    v[h][l]=1;
    int x,y;
    for(int i=0;i<8;++i)
    {
        x=h+a[i][0];
        y=l+a[i][1];
        if(x>=0&&x<m&&y>=0&&y<n&&v[x][y]==0&&p[x][y]=='@')
            dfs(x,y);
    }
}
int main()
{
    //cout << "Hello world!" << endl;
    while(scanf("%d %d",&m,&n)&&m!=0&&n!=0)
    {
        for(int i=0;i<m;++i)
            scanf("%s",p[i]);
        memset(v,0,sizeof(v));
        int bh=0;
        for(int i=0;i<m;++i)
            for(int j=0;j<n;++j)
        {
            if(p[i][j]=='@'&&v[i][j]==0)
            {
                dfs(i,j);
                ++bh;
            }

        }
        printf("%dn",bh);
    }
    return 0;
}

最后

以上就是激昂冥王星为你收集整理的uva 572 - Oil Deposits的全部内容，希望文章能够帮你解决uva 572 - Oil Deposits所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。