POJ 1562 Oil Deposits

转载请注明出处：http://blog.****.net/a1dark

大规模的图论切题之旅正式开始了、由于今天停了一天的电、所以晚上才开始切题、直到昨晚才把图论大概看了一遍、虽然网络流部分还是不怎么懂、但是也懂得了一些基础的算法、相信只要不断的刷题、必然可以可以搞懂、至于连通和匹配还是只是有那么一些概念、只会一些模板、等做题做多了自然就会懂了、努力切题中。。。

分析：刚开始水一发、这题很简单、应该尽量1次做对、一个简单的图的DFS搜索、思路就不讲了、看看代码应该没什么问题、

#include<stdio.h>
#include<string.h>
int dir[8][2]={0,1,1,0,0,-1,-1,0,1,1,1,-1,-1,1,-1,-1};
char map[150][150];
int m,n;
void dfs(int x,int y){
    if(map[x][y]=='*')
        return;
    map[x][y]='*';
    for(int i=0;i<8;i++){
        int tx=x+dir[i][0];
        int ty=y+dir[i][1];
        if(tx<1||tx>m||ty<1||ty>n)continue;
        if(map[tx][ty]=='@')
            dfs(tx,ty);
    }
    return;
}
int main(){
    int i,j;
    while(scanf("%d%d",&m,&n)!=EOF){
        memset(map,'\0',sizeof(map));
        if(m==0)break;
        for(i=1;i<=m;i++)
            scanf("%s",map[i]+1);
        int ans=0;
        for(i=1;i<=m;i++)
            for(j=1;j<=n;j++)
                if(map[i][j]=='@'){
                    dfs(i,j);
                    ans++;
                }
        printf("%d\n",ans);
    }
    return 0;
}