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