一篇搞懂深搜DFS

核心代码：

关于dfs参数问题，什么在变化，就把什么设置成参数。

void dfs()//参数用来表示状态  
{  
    if(到达终点状态)  
    {  
        ...//根据题意添加  
        return;  
    }  
    if(越界或者是不合法状态)  
        return;  
    if(特殊状态)//剪枝
        return ;
    for(扩展方式)  
    {  
        if(扩展方式所达到状态合法)  
        {  
            修改操作;//根据题意来添加  
            标记；  
            dfs（）；  
            (还原标记)；  
            //是否还原标记根据题意  
            //如果加上（还原标记）就是 回溯法  
        }  
 
    }  
} 

 先看模板，到这里伙计们肯定不理解到底什么含义，所以我在这里解释下，涉及到深搜的基本提，全是这个套路，现在不理解，先把框架记住，然后用框架去刷几道题就会发现新大陆了

现在，上一道深搜的考题

有一个大小为N×MN×M N\times MN×M的园子，雨后积起了水。八连通的积水被认为是连接在一起的。请求出园子里总共有多少水洼？八连通指的是下图中相对W的∗部分，‘W’表示积水，’ * '表示没有积水。

输入

10 12
W********WW*
*WWW*****WWW
****WW***WW*
*********WW*
*********W**
**W******W**
*W*W*****WW*
W*W*W*****W*
*W*W******W*
**W*******W*

输出

3

问题分析

首先定义一个二维数组存储这片下过雨的区域，然后双重for循环遍历一下，每次找到一个 ‘W’ 就记一次数，代表这里有一个水洼，如果继续遍历下去会找到与前面 ‘W’ 相连通的积水，而题上说了只要是相连通的积水就算是一个水洼，因此直接这样遍历是不行的。

为了解决这个重复计算的问题，可以定义一个作为递归的方法，将这个 ‘W’ 的坐标传入，并将这个积水去处，‘W’ 变为 ’ * ’ ,然后以这个坐标为中心，遍历它的八个方向，看看能不能找到下一个 ‘W’ ，找到后向下进行递归，将这个’W’传入本方法，继续进行去除，遍历，直到再也找不到相连通的积水，就表示这一处水洼全部清除了，完美解决重复计算的问题，也解决了两个相连通的积水相互找到对方，陷入无限递归的局面。

代码实现

import java.util.Scanner;
 
public class NumberOfPuddles {
	static int n, m;
	static char[][] field;
 
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		field = new char[n][];
		for (int i = 0; i < n; i++) {
			field[i] = sc.next().toCharArray();
		}
		int count = 0;	//计数器
		for (int i = 0; i < field.length; i++) {
			for (int j = 0; j < field[i].length; j++) {
				// 枚举整个n*m的园子，每找到一个'W'就代表找到了一个水洼
				// 然后用深搜的方式将连通的所有积水全部去除，防止重复计算
				if (field[i][j] == 'W') {
					count++;
					dfs(i, j);
				}
			}
		}
		System.out.println(count);
	}
 
	private static void dfs(int i, int j) {
		field[i][j] = '*';	//清除积水
		//遍历八个方向找到连通的积水
		for (int p = i - 1; p <= i + 1; p++) {
			for (int q = j - 1; q <= j + 1; q++) {
				if (p >= 0 && p < n && q >= 0 && q < m) {
					if (field[p][q] == 'W') {
						dfs(p, q);
					}
				}
 
			}
		}
	}
}

到这里，小伙伴们估计还是疑问很大，那么请仔细的对着框架，看这道题，看这个题的代码是不是和框架几乎一模一样啊。

深搜深层分析

题型分类：

写过这些入门题后，我们可以将DFS题分为两大类：


1 . 地图型：这种题型将地图输入，要求完成一定的任务。因为地图的存在。使得题意清楚形象化，容易理清搜索思路。

    AOJ 869-迷宫(遍历地图，四向搜索)
    HDU 1035-Robot Motion(指定方向搜索，迷路（循环）判断)HDU 1035-Robot Motion(指定方向搜索，迷路（循环）判断)
    HDU 1045-Fire Net(check函数，回溯)
 

2 . 数据型：这种题型没有给定地图，一般是一串数字或字母，要求按照一定的任务解题。相对于地图型，这种题型较为抽象，需要在数据中进行搜索。数据以数组的形式存储，那么只要将数组也当作一张图来进行搜索就可以了。

    HDU 1016-Prime Ring Problem(回溯、素数筛)
    HDU 1258-Sum It Up(双重DFS递归，去重技巧)
    HDU 1015-Safecraker(回溯，字符处理)
    HDU 2676-Sudoku(抽象，回溯)

（这里不列举了，全是一个大佬写的文章）