HDU 1241：Oil Deposits（dfs+染色）

题目链接

题意：
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;
}