基础搜索题――油田合并(深度搜索) - c++编程基础

某石油公司发现了一个油田。该油田由n*m个单元组成的矩形，有些单元里有石油，有些则没有。单元油田可以通过上，下，左或右连通。在一个单元油田里架设一台采油机，它可以把和该单元油田相连的单元油田的石油采完。该公司想知道最少需要架设几台采油机能把所有的石油采完？

输入

先输入2个正整数n，m(1<=n,m<=50)。接着有n行，每行有m个字符。'@'表示该单元有石油，'*'则表示该单元没有石油。

输入到文件结束。

输出

对于每组测试，输出最少需要架设几台采油机。

样例输入

2 2

样例输出

解题报告：

此题的程序用的是深度优先搜索，开始设一个变量many，表示找到了多少块油田，初始值为0，接着可以从第一块土地开始搜索，当遇到没有标号的油田时，用深度搜索把与这块油田相连的其他油田全部标号，并且many ++;当把整个地图都全部扫描完毕后，最后只需要输出many的值即可。

代码实现：

#include  
#include  
#include  
char s[55][55];  
int map[55][55];  
int dfs(int i,int j);//深度搜索  
int n,m,many;  
int main()  
{  
    while(scanf("%d%d",&n,&m)!=EOF)  
    {  
        many=0;  //给many 初始化  
        memset(map,0,sizeof(map));//给map数组初始化  
        for(int i=0;i=0&&s[i-1][j]=='@'&&map[i-1][j]==0)//判断(i-1,j)这个点是否符合条件  
        dfs(i-1,j);  
    if(j-1>=0&&s[i][j-1]=='@'&&map[i][j-1]==0)//判断(i,j-1)这个点是否符合条件  
        dfs(i,j-1);  
    return 1;  //搜索完成后返回1 使mang+=1;  
}