uva_572 - Oil Deposits

 
[cpp] 
/* 題目大意：一塊區域中分布著油田，連在一起就屬於一個油田，求油田個數。
 * 也就是求一個無向圖的連通分支個數，直接dfs8個方向，水過。。。
*/ 
#include <cstdio> 
#include <cstring> 
#include <algorithm> 
using namespace std; 
 
#define MAX 101 
#define DIR 8 
 
char a[MAX][MAX]; 
int visited[MAX][MAX]; 
int dir[][2] = {  www.2cto.com
    {-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, 
    {0, 1}, {1, -1}, {1, 0}, {1, 1} 
}; 
 
void DFS(int x, int y){ 
    if( visited[x][y] || a[x][y] == '*' ) return ; 
    visited[x][y] = 1; 
    for(int i = 0; i < DIR; i ++) 
        DFS(x+dir[i][0], y+dir[i][1]); 
} 
 
int main(int argc, char const *argv[]) 
{ 
#ifndef ONLINE_JUDGE 
        freopen("test.in", "r", stdin); 
#endif 
    int m, n, ans; 
    while( scanf("%d %d", &m, &n), m || n ){ 
        ans = 0; 
        memset(a, '*', sizeof(a)); 
        memset(visited, 0, sizeof(visited)); 
 
        for(int i = 0; i < m; i ++){ 
            getchar(); 
            for(int j = 0; j < n; j ++){ 
                scanf("%c", &a[i][j]); 
            } 
        } 
        for(int i = 0; i < m; i ++){ 
            for(int j = 0; j < n; j ++){ 
                if( a[i][j] == '@' && !visited[i][j] ){ 
                    ans ++; 
                    DFS(i, j); 
                } 
            } 
        } 
        printf("%d\n", ans); 
    } 
    return 0; 
}