HDU 1241 Oil Deposits[dfs || bfs]

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1241

题目的意思很简单，问你有多少块油田。。‘@’表示油田，‘*’表示不是油田。。连在一起的油田属于同一个油田。。八个方向相邻被称为连在一起。。

直接bfs或dfs都行。。时间复杂度为O(m)。m为‘@’个数。。

分别用dfs和bfs实现了一下。。时间差不多。。原因吗？都是走过以后就不用在走了。。

bfs Code:

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
using namespace std;

const int N = 1e2 + 5;
const int dx[] = {0, 0, 1, 1, 1, -1, -1, -1};
const int dy[] = {1, -1, -1, 0, 1, -1, 0, 1};
int n, m;
char map[N][N];

struct Node
{
    int x, y;
    Node() {}
    Node(int a, int b){
        x = a;
        y = b;
    }
};

void bfs(int bx, int by)
{
    queue<Node> q;
    q.push(Node(bx, by));
    map[bx][by] = '*';
    while(!q.empty()){
        Node tmp = q.front(), tmp1;
        q.pop();
        for(int i = 0 ; i < 8; i ++){
            tmp1.x = tmp.x + dx[i]; tmp1.y = tmp.y + dy[i];

            if(tmp1.x < 1 || tmp1.x > n || tmp1.y < 1 || tmp1.y > m || map[tmp1.x][tmp1.y] == '*') continue;
            q.push(tmp1);
            map[tmp1.x][tmp1.y] = '*';
        }
    }
    return ;
}

int main()
{
    while(scanf("%d %d", &n, &m) && (n || m)){
        getchar();
        for(int i = 1; i <= n; i ++){
            for(int j = 1; j <= m; j ++)
            scanf("%c", &map[i][j]);
            getchar();
        }
        int ans = 0;
        for(int i = 1; i <= n; i ++){
            for(int j = 1; j <= m; j ++)
            if(map[i][j] == '@') {
                bfs(i, j); ans ++;
            }
        }
        cout << ans << endl;
    }
    return 0;
}
           

dfs Code：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

const int N = 105;
const int dx[] = {0, 0, 1, 1, 1, -1, -1, -1};
const int dy[] = {1, -1, -1, 0, 1, -1, 0, 1};
char map[N][N];
int n, m;

void dfs(int x, int y)
{
//    cout << "now = " << x << ' ' << y << endl;
    for(int i = 0; i < 8; i ++){
        int gox = x + dx[i], goy = y + dy[i];
        if(gox < 1 || gox > n || goy < 1 || goy > m || map[gox][goy] == '*') continue;
        map[gox][goy] = '*';
        dfs(gox, goy);
    }
    return ;
}

int main()
{
//    freopen("1.txt", "r", stdin);
    while(scanf("%d %d", &n, &m) && (n || m)){
        getchar();
        for(int i = 1;  i <= n; i ++){
            for(int j = 1; j <= m; j ++)
            scanf("%c", &map[i][j]);
            getchar();
        }
        int ans = 0;
        for(int i = 1; i <= n; i ++){
            for(int j = 1; j <= m; j ++){
                if(map[i][j] == '@'){
                    map[i][j] = '*';
                    dfs(i, j);
                    ans ++;
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}
           

dfs还是比较好玩的。。