DFS-“计算油田数量”

背景：最近一直在准备考研复试，就又温习了一次算法。

首先来看看DFS吧。

题目：选自POJ1562

GeoSurvComp地质探测公司负责探测地下油田。每次GeoSurvComp公司都是在一块长方形的土地上来探测油田。在探测时，他们把这块土地用网格分成若干个小块，然后逐个分析每块土地，用探测设备探测地下是否有油田。土地底下有油田则成为pocket，如果两个pocket相邻，则认为是同一块油田，油田可能覆盖多个pocket。试计算长方形的土地上有多少个不同的油田。

输入描述：

输入文件中包含多个测试数据，每个测试数据描述了一个网格。每个网格数据的第1行为两个整数：m、n，分别表示网格的行和列；如果m=0，则表示输入结束，否则1<=m<=100，1<=n<=100。接下来有m行数据，每行数据有n个字符（不包括行结束符）。每个字符代表一个小方块，如果为“*”，则代表没有石油，如果为“@”，则代表有石油，是一个pocket。

输出描述：

对输入文件中的每个网格，输出网格中不同的油田数目。如果两块不同的pocket在水平、垂直或者对角线方向上相邻，则被认为属于同一块油田。每块油田所包含的pocket数目不会超过100。

样例输入：

5 5

****@

*@@*@

*@**@

@@@*@

@@**@

样例输出：

2
 

对代码的学习与思考

遍历每行每列，当碰到@时，就使用DFS向周围的8个方向进行搜索，看看有没有相连的@。大概就是下图这个意思。

（i-1,j-1）	（i-1,j）	（i-1,j+1）
（i,j-1）	（i,j）	（i,j+1）
（i+1,j-1）	（i+1,j-1）	（i+1,j-1）

 

在走过一个点时，将其赋值为*，表示已经走过了，再次遍历时不会重复。

好久没有温习算法了，其实研究算法还是挺有意思的。希望自己也能成为算法大手子。

#include<iostream>
#include<memory.h>
using namespace std;
 char map[101][101];
 int row,colunm,count=0;
void Dfs(int x,int y)
{
    if(x<0 || y<0 || x >= row || y >= colunm || map[x][y]=='*')//查看对（x，y）是否已经出界，或者不是@
        return;
    else
    {
        map[x][y]='*';//对走过的路进行标记，再次递归时，不会重复
        Dfs(x-1,y-1);//对8个方向进行递归
        Dfs(x-1,y);
        Dfs(x-1,y+1);
        Dfs(x,y-1);
        Dfs(x,y+1);
        Dfs(x+1,y-1);
        Dfs(x+1,y);
        Dfs(x+1,y+1);
    }
}
int main()
{
    while(cin>>row>>colunm)
    {
        if (row == 0 || colunm == 0)
            break;
        memset(map, '*', sizeof(map));//初始化数组
        for (int i=0;i<row;i++) {
            for (int j=0;j<colunm;j++) {
                cin>>map[i][j];
            }
        }

        for (int i=0;i<row;i++) {
            for (int j=0;j<colunm;j++) {
                if(map[i][j]=='@')
                {
                    Dfs(i,j);
                    count++;
                }
            }
        }
        cout<<count<<endl;
    }
    return 0;

}

 

最后祝福自己考研成功！