DFS

朴灿烈づ我的快乐病毒、 2022-08-03 16:56 166阅读 0赞

## 深优的话，占内存少，能找到最优解（一定条件下），但能很快找到接近解（优点），可能不必遍历所有分枝（也就是速度快）, 深优的一个应用就是连连看游戏. ##

深度优先搜索法有递归以及非递归两种设计方法。一般的，当搜索深度较小、问题递归方式比较明显时，用递归方法设计好，它可以使得程序结构更简捷易懂。当数据量较大时，由于系统堆栈容量的限制，递归容易产生溢出，用非递归方法设计比较好。不一定会得到最优解，这个时候需要修改原算法：把原输出过程的地方改为记录过程，即记录达到当前目标的路径和相应的路程值，并与前面已记录的值进行比较，保留其中最优的，等全部搜索完成后，才把保留的最优解输出。

一般来说，广搜常用于找单一的最短路线，或者是规模小的路径搜索，它的特点是"搜到就是最优解"， 而深搜用于找多个解或者是"步数已知（好比3步就必需达到前提）"的标题，它的空间效率高，然则找到的不必定是最优解，必需记实并完成全数搜索，故一般情况下，深搜需要很是高效的剪枝（优化）.

像搜索最短路径这些的很显著若是用广搜，因为广搜的特征就是一层一层往下搜的，保证当前搜到的都是最优解，当然，最短路径只是一方面的操作，像什么起码状态转换也是可以操作的。

深搜就是优先搜索一棵子树，然后是另一棵，它和广搜对比，有着内存需要相对较少的所长，八皇后标题就是典范楷模的操作，这类标题很显著是不能用广搜往解决的。或者像图论里面的找圈的算法，数的前序中序后序遍历等，都是深搜。

hdu1241可以看作是dfs的简单模板

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

#include <iostream>
    #include <cstring>
    using namespace std;
    
    const int MAX=101;
    int m,n;
    char map[MAX][MAX];   //地图
    int dir[8][2]={0,1,1,0,0,-1,-1,0,1,1,-1,-1,1,-1,-1,1};  //8个移动方向
    
    void dfs(int x,int y){
    	map[x][y]='*';  //已遍历，记为*，防止二次遍历
    	for (int i = 0;i < 8;i++)
    	{
    		//往（x，y）剩下的8个方向遍历
    		int x1 = x + dir[i][0];
    		int y1 = y + dir[i][1];
    		if (x1>=0&&y1>=0&&x1<m&&y1<n&&map[x1][y1]=='@')   //m,n的位置不能搞错
    		{
    			dfs(x1,y1);   // 符合条件的继续遍历它的8个方向
    		}
    	}
    }
    
    int main(){
    	int ans;
    	while (cin>>m>>n&&(m||n))
    	{
    		ans = 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]=='@')
    				{
    					dfs(i,j);
    					ans+=1;
    				}
    			}
    		}
    		cout<<ans<<endl;
    	}
    	return 0;
    }