`
isiqi
  • 浏览: 15946086 次
  • 性别: Icon_minigender_1
  • 来自: 济南
社区版块
存档分类
最新评论

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






分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics