【题解】Reach-Top OJ [1115] 勘探油田

题目描述

某石油勘探公司正在按计划勘探地下油田资源，工作在一片长方形的地域中。他们首先将该地域划分为许多小正方形区域，然后使用探测设备分别探测每一块小正方形区域内是否有油。若在一块小正方形区域中探测到有油，则标记为’ $@$ ’，否则标记为’ $*$ ’。如果两个相邻区域都为 $1$ ，那么它们同属于一个石油带，一个石油带可能包含很多小正方形区域，而你的任务是要确定在一片长方形地域中有多少个石油带。所谓相邻，是指两个小正方形区域上下、左右、左上右下或左下右上同为’ $@$ ’。

输入

输入数据将包含一些长方形地域数据，每个地域数据的第一行有两个正整数 $m$ 和 $n$ ，表示该地域由 $m×n$ 个小正方形所组成，如果 $m$ 为 $0$ ，表示所有输入到此结束；否则，后面 $m$ （ $1≤m≤100$ ）行数据，每行有 $n$ （ $1≤n≤100$ ）个字符，每个字符为’ $@$ ’或’ $*$ ’，表示有油或无油。每个长方形地域中，’ $@$ ’的个数不会超过 $100$ 。

输出

每个长方形地域，输出油带的个数，每个油带值占独立的一行。油带值不会超过100。

样例输入

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

样例输出

思路&解答

经典的连通块题目，使用DFS搜索。
题意让我们求油田的块数，也就是求联通块数。
首先先要清楚搜索方向，我们将当前格定义为 $(x,y)$ ，则以此格可推出其他八格分别为：

$(x+1,y),(x-1,y),(x,y+1),(x,y-1),(x+1,y+1),(x-1,y-1),(x+1,y-1),(x-1,y+1)$ 。
如下图：

故我们的方向函数gox[],goy[]为:

const int gox[] = { 1,-1,0,0,1,-1,1,-1 };
const int goy[] = { 0,0,1,-1,1,-1,-1,1 };

扫描全局见到' $@$ '时调用DFS(int x,int y)函数，并且计数器sum自增 $1$ 。
我们把每次走到的一格都标记为' $*$ '，把油田覆盖为平地，以免重复计数。
再次覆盖一整块油田，如此反复直到所有的地均为' $*$ '时结束。
完整的DFS(int x,int y)函数为：

void DFS(int x, int y)
{
    mp[x][y] = '*'; //mp[][]是存放地图的二维数组哦~~
    for (int i = 0; i < 8; i++)
    {
        int next_x = x + gox[i];
        int next_y = y + goy[i];
        if (next_x > 0 && next_y > 0 && next_x <= m && next_y <= n && mp[next_x][next_y] == '@')
            DFS(next_x, next_y); //下一步扫描
    }
}

最后，输出计数器的sum即可。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 105;
const int gox[] = { 1,-1,0,0,1,-1,1,-1 };
const int goy[] = { 0,0,1,-1,1,-1,-1,1 };
char mp[maxn][maxn];
int m, n;
void DFS(int x, int y)
{
    mp[x][y] = '*';
    for (int i = 0; i < 8; i++)
    {
        int next_x = x + gox[i];
        int next_y = y + goy[i];
        if (next_x > 0 && next_y > 0 && next_x <= m && next_y <= n && mp[next_x][next_y] == '@')
            DFS(next_x, next_y);
    }
}
int main()
{
    while (cin >> m >> n && m)
    {
        int sum = 0;
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                cin >> mp[i][j];
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                if (mp[i][j] == '@')
                {
                    DFS(i, j);
                    sum++;
                }
        cout << sum << endl;
    }
    return 0;
}