uva 572 - Oil Deposits

題目意思：給你一塊區域裡面分布著油田，只要有連著就屬於同一個油田，求出該區域有幾個油田

解題思路：簡單的Bfs 或 dfs 可以搞定 ,注意對走過的進行標記用mark數組。

代碼:

[cpp] 
<span style="font-size:18px;">//DFS代碼（用到遞歸） 
#include <iostream> 
#include <queue> 
#include <cstdio> 
#include <cstring> 
using namespace std; 
 
const int MAXN = 110; 
int n , m , sum; 
char ch[MAXN][MAXN]; 
int mark[MAXN][MAXN];//標記是否走過 
int x[8] = {-1,-1,0,1,1,1,0,-1};//方向數組 
int y[8] = {0,1,1,1,0,-1,-1,-1}; 
 
//搜索 
void dfs(int i , int j){ 
    if(mark[i][j] == 1) 
        return; 
    for(int k = 0 ; k < 8 ; k++){ 
        if(i+x[k]<0 || i+x[k]>=m || j+y[k]<0 || j+y[k]>=n)//越界 
            continue; 
        if(ch[i+x[k]][j+y[k]] == '*')//沒用的字符 
            continue; 
        if(ch[i+x[k]][j+y[k]] == '@'){//繼續下一步遞歸 
            mark[i][j] = 1; 
            dfs(i+x[k] , j+y[k]); 
        } 
    } 
} 
 
//處理問題函數 
void solve(){ 
    int i , j;  
    sum = 0; 
    memset(mark , 0 , sizeof(mark)); 
    for(i = 0 ; i < m ; i++){ 
        for(j = 0 ; j < n ; j++){ 
            if(ch[i][j] == '@' && mark[i][j] == 0){ 
                sum++; 
                dfs(i , j); 
            } 
        } 
    } 
    cout<<sum<<endl; 
} 
 
//主函數 
int main(){ 
    while(scanf("%d%d%*c" , &m , &n) && m && n){ 
        for(int i= 0 ; i < m ; i++){ 
            for(int j= 0 ; j < n ; j++) 
                scanf("%c" , &ch[i][j]); 
            getchar(); 
        } 
        solve(); 
    } 
} 
 
//BFS代碼（用到隊列） 
#include <iostream> 
#include <queue> 
#include <cstdio> 
#include <cstring> 
using namespace std; 
 
const int MAXN = 110; 
int n , m , sum; 
char ch[MAXN][MAXN]; 
int mark[MAXN][MAXN]; 
int x[8] = {-1,-1,0,1,1,1,0,-1}; 
int y[8] = {0,1,1,1,0,-1,-1,-1}; 
queue<char>q; 
 
 
//廣搜 
void Bfs(int i , int j){ 
    if(q.empty()|| mark[i][j] == 1) 
        return; 
    if(!q.empty()){ 
        for(int k = 0 ; k < 8 ; k++){ 
            if(i+x[k]<0 || i+x[k]>=m || j+y[k]<0 || j+y[k]>=n) 
                continue; 
            if(ch[i+x[k]][j+y[k]] == '*') 
                continue; 
            if(ch[i+x[k]][j+y[k]] == '@'){ 
                q.pop();//第一個出對 
                q.push('@');//入對 
                mark[i][j] = 1; 
                Bfs(i+x[k] , j+y[k]);//可以這裡去掉在外面改為while循環 
            } 
        } 
    } 
} 
 
//處理問題函數 
void solve(){ 
    int i , j;  
    sum = 0; 
    memset(mark , 0 , sizeof(mark)); 
    for(i = 0 ; i < m ; i++){ 
        for(j = 0 ; j < n ; j++){ 
            if(ch[i][j] == '@' && mark[i][j] == 0){ 
                sum++; 
                q.push('@'); 
                Bfs(i , j); 
            } 
        } 
    } 
    cout<<sum<<endl; 
} 
 
//主函數 
int main(){ 
    while(scanf("%d%d%*c" , &m , &n) && m && n){ 
        for(int i= 0 ; i < m ; i++){ 
            for(int j= 0 ; j < n ; j++) 
                scanf("%c" , &ch[i][j]); 
            getchar(); 
        } www.2cto.com
        solve(); 
    } 
} 
 
 
 
 
</span> 
作者：cgl1079743846