poj 1562 油田(Oil Deposits) DFS

地址   http://poj.org/problem?id=1562

油田(Oil Deposits)

题目来源：

Mid-Central USA 1997, ZOJ1709, POJ1562

题目描述：

GeoSurvComp 地质探测公司负责探测地下油田。每次 GeoSurvComp 公司都是在一块长方

形的土地上来探测油田。在探测时，他们把这块土地用网格分成若干个小方块，然后逐个分析每

块土地，用探测设备探测地下是否有油田。方块土地底下有油田则称为 pocket，如果两个 pocket

相邻，则认为是同一块油田，油田可能覆盖多个 pocket。你的工作是计算长方形的土地上有多少

个不同的油田。

输入描述：

输入文件中包含多个测试数据，每个测试数据描述了一个网格。每个网格数据的第一行为两

个整数：m n，分别表示网格的行和列；如果 m = 0，则表示输入结束，否则 1≤m≤100，1 ≤n

≤100。接下来有 m 行数据，每行数据有 n 个字符（不包括行结束符）。每个字符代表一个小方块，

如果为“*”，则代表没有石油，如果为“@”，则代表有石油，是一个 pocket。

输出描述：

对输入文件中的每个网格，输出网格中不同的油田数目。如果两块不同的 pocket 在水平、垂

直、或者对角线方向上相邻，则被认为属于同一块油田。每块油田所包含的 pocket 数目不会超过

100。

Sample Input

1 1
*
3 5
*@*@*
**@**
*@*@*
1 8
@@****@*
5 5 
****@
*@@*@
*@**@
@@@*@
@@**@
0 0

Sample Output

0
1
2
2

 

本题比较简单  常规DFS 

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <memory.h>

using namespace std;

const int MAX_SIZE = 100;

char g[MAX_SIZE][MAX_SIZE];

int n, m;
int oilCount = 0;

int addx[] = { -1,-1,-1,0,0,1,1,1};
int addy[] = { -1,0,1,-1,1,-1,0,1};


void DFS(int x,int y)
{
    if (x < 0 || x >= n || y < 0 || y >= m) return;
    if (g[x][y] != '@') return;
    g[x][y] = '*';
    for (int i = 0; i < 8; i++) {
        int newx = x + addx[i];
        int newy = y + addy[i];

        DFS(newx, newy);
    }
}


int main()
{
    while (1) {
        cin >> n >> m;
        if (n == m && m == 0) break;
        memset(g, 0, sizeof g);
        oilCount = 0;
        for (int i = 0; i < n; i++) {
            scanf("%s",g[i]);
        }
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (g[i][j] == '@') {
                    DFS(i, j);
                    oilCount++;
                }
            }
        }

        cout << oilCount << endl;
    }


    return 0;
}