HDU 1241 Oil Deposits (DFS or BFS)

**链接 : ** Here!

**思路 : ** 搜索判断连通块个数, 所以 $DFS$ 或则 $BFS$ 都行喽...., 首先记录一下整个地图中所有$Oil$的个数, 然后遍历整个地图, 从油田开始搜索它所能连通多少块其他油田, 只需要把它所连通的油田个数减去, 就ok了

/*************************************************************************

	> File Name: E.cpp

	> Author:

	> Mail:

	> Created Time: 2017年11月26日 星期日 10时51分05秒

 ************************************************************************/

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

#define MAX_N 150

int n, m;

int total_num;

int  vis[MAX_N][MAX_N];

int dx[8] = {0, 0, -1, 1, 1, -1, 1, -1};

int dy[8] = {-1, 1, 0, 0, 1, -1, -1, 1};

char G[MAX_N][MAX_N];

void dfs(int x, int y) {

    vis[x][y] = 1;

    for (int i = 0 ; i < 8 ; ++i) {

        int now_x = x + dx[i];

        int now_y = y + dy[i];

        if (vis[now_x][now_y]) continue;

        if (now_x < 0 || now_x >= n || now_y < 0 || now_y >= m) continue;

        if (G[now_x][now_y] != '@') continue;

        vis[now_x][now_y] = 1;

        --total_num;

        dfs(now_x, now_y);

    }

}

void solve() {

    for (int i = 0 ; i < n ; ++i) {

        for (int j = 0 ; j < m ; ++j) {

            if (G[i][j] == '@') {

                ++total_num;

            }

        }

    }

    memset(vis, 0, sizeof(vis));

    for (int i = 0 ; i < n ; ++i) {

        for (int j = 0 ; j < m ; ++j) {

            if (G[i][j] != '@' || vis[i][j]) continue;

            dfs(i, j);

        }

    }

}

int main() {

    while (scanf("%d%d", &n, &m) != EOF) {

        if (n == 0 && m == 0) break;

        memset(G, 0, sizeof(G));

        total_num = 0;

        for (int i = 0 ; i < n ; ++i) {

            getchar();

            scanf("%s", G[i]);

        }

        solve();

        printf("%d\n", total_num);

    }

    return 0;

}

巴特西

HDU 1241 Oil Deposits (DFS or BFS)

最新文章

热门文章