2015年4月4日星期六

[UVa] 572 - Oil Deposits

有點像POJ2386 Lack Counting(其實幾乎一樣)
DFS用遞迴實作,遇到油田就換成*字號
每一個DFS結束後計數即可

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int m,n;
/*
    n
  *@*@
 m@**@
  *@*@
*/
char deposits[120][120];
void dfs(int x, int y){
    deposits[x][y]='*';
    int dx,dy,nx,ny;
    for(dx=-1;dx<=1;dx++){
        for(dy=-1;dy<=1;dy++){
            nx = x+dx;
            ny = y+dy;
            //printf("dx=%d dy=%d\n",dx,dy);
            if(nx>=0 && nx<m && ny>=0 && ny<n && deposits[nx][ny]=='@')
                dfs(nx,ny);
        }
    }
}
int main(){
    freopen("input.txt","r",stdin);
    while(scanf("%d %d",&m,&n)!=EOF){
      getchar(); //remove the newline char above
        if(m==0)break;
        for(int i=0;i<m;i++){
          fgets(deposits[i],sizeof(deposits[i]),stdin);
        }
        /* Print */
        /*
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                printf("%c",deposits[i][j]);
            }
            printf("\n");
        }
        */
        int count=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(deposits[i][j]=='@'){
                    dfs(i,j);
                    count++;
                }
            }
        }
        printf("%d\n",count);
    }
    return 0;
}

沒有留言: