HDU 1241：Oil Deposits（dfs+染色）

蔚落 2023-07-07 15:57 38阅读 0赞

# HDU 1241：Oil Deposits（dfs+染色） #

[题目链接][Link 1]

**题意：**  
n\* m的方块，代表一块大油田；其中’@‘表示该位置有油，’\*'代表该位置没有油；求有多少小块油田  
（需要注意的是：彼此相连的都属于同一块小油田：其中就包括上、下、左、右、对角线方向）

**题解：**  
一开始想到的就是并查集；发现似乎并不是特别简单，如果是方阵的可能会好处理点；  
然后想了好久，其实就是一个染色问题啊，直接**dfs+剪枝+染色**即可

#include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #include<iostream>
    #include<sstream>
    #include<string>
    #include<queue>
    #include<vector>
    #include<set>
    #include<stack>
    #include<map>
    #define lowbit(x) x&(-x)
    #define ll long long
    #define inf 0x3f3f3f3f
    using namespace std;
    const int maxn=1e5+10;
    int n,m;
    char mp[110][110];
    int vis[110][110];
    int cnt;
    int dirx[9]={
        0,-1,-1,0,1,1,1,0,-1};
    int diry[9]={
        0,0,1,1,1,0,-1,-1,-1};
    void init(){
        
        memset(mp,0,sizeof(mp));
        memset(vis,0,sizeof(vis));
        cnt=0;
    }
    int check(int x,int y){
        
        if(x>=1&&x<=n&&y>=1&&y<=m&&vis[x][y]==0&&mp[x][y]=='@'){
        
            return 1;
        }
        else
            return 0;
    }
    void dfs(int x,int y){
        
        for(int i=1;i<=8;i++){
        
            int fx=x+dirx[i];
            int fy=y+diry[i];
            if(check(fx,fy)){
        
                vis[fx][fy]=1;
                mp[fx][fy]='*';
                dfs(fx,fy);
            }
        }
        return ;
    }
    int main(){
        
        while(~scanf("%d%d",&n,&m)){
        
            if(n==0&&m==0)
                break;
            init();
            for(int i=1;i<=n;i++){
        
                scanf("%s",mp[i]+1);
            }
            for(int i=1;i<=n;i++){
        
                for(int j=1;j<=m;j++){
        
                    if(check(i,j)){
        
                        cnt++;
                        vis[i][j]=1;
                        mp[i][j]='*';
                        dfs(i,j);
                    }
                }
            }
            cout<<cnt<<endl;
        }
        return 0;
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=1241