【UVA 572】Oil Deposits 题解（深度优先搜索）

GeoSurvComp地质调查公司负责探测地下石油矿床。 GeoSurvComp一次处理一个大的矩形土地区域，并创建一个划分 将土地分割成许多方形地块。然后使用传感设备分别分析每个地块 确定图中是否含有油。 含有石油的地块称为口袋。如果两个口袋相邻，则它们是 相同的油沉积。油沉积物可能非常大，并且可能包含许多气穴。你的工作是 确定网格中包含多少不同的油沉积物。 输入 输入文件包含一个或多个网格。每个网格以一条包含m和n的线开始 网格中的行和列，由单个空间分隔。如果m＝0，则表示输入结束； 否则1≤m≤100，1≤n≤100。下面是m行，每行n个字符（不计在内 行尾字符）。每个字符对应一个绘图，并且是“*”，表示 无油，或“@”，表示油袋。 输出 对于每个网格，输出不同石油沉积物的数量。两个不同的口袋是相同的一部分 如果它们水平、垂直或对角相邻，则会沉积油。油沉积物不会包含 超过100个口袋。

Sample Input 1 1 * 3 5 @@* @@@* 1 8 @@***@ 5 5 ****@ @@@ @**@ @@@@ @@**@ 0 0 Sample Output 0 1 2 2

思路

用一个二维数组储存图。对图进行遍历，若找到@，则将其替换为*,计数器加一，然后对该位置的八个方向进行搜索，把@替换为*。注意搜索时需要判断是否出界。

AC代码

#include <iostream>
using namespace std;
#define AUTHOR "HEX9CF"

const int maxn = 105;

int m, n;
char map[maxn][maxn];
int cnt;

void dfs(int x, int y)
{
    map[x][y] = '*';
    for (int i = x - 1; i <= x + 1; i++)
    {
        for (int j = y - 1; j <= y + 1; j++)
        {
            if ('@' == map[i][j] && i >= 0 && i < m && j >= 0 && j < n)
            {
                dfs(i, j);
            }
        }
    }
}

void print()
{
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cout << map[i][j];
        }
        cout << endl;
    }
}

int main()
{
    while (1)
    {
        cnt = 0;
        cin >> m >> n;
        if (!m && !n)
        {
            return 0;
        }
        cnt = 0;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                cin >> map[i][j];
            }
        }
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if ('@' == map[i][j])
                {
                    cnt++;
                    dfs(i, j);
                }
            }
        }
        // print();
        cout << cnt << endl;
    }
    return 0;
}