uva 572 - Oil Deposits

点击打开链接

题目意思：给你一块区域里面分布着油田，只要有连着就属于同一个油田，求出该区域有几个油田

解题思路：简单的Bfs 或 dfs 可以搞定 ,注意对走过的进行标记用mark数组。

代码:

//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();
        }
        solve();
    }
}