深度优先DFS搜索
什么是深度优先搜索？
深度优先搜索（DFS ,Depth-First Search）是搜索手段之一。它从某个状态，不断地转移状态直到无法转移，然后回退到前一步的状态，继续转移到其他状态，如此不断重复，直到找到最终的解。
如何实现深度优先搜索？
根据深度优先搜索的特点，采用递归函数实现比较简单。
算法实例
实例一：若干数和为k的问题。
题干：给定整数a1,a2......an。判断是否可以从中选出若干数，使他们的和为k(数不能加重复的)
限制条件：
1<=n<=20
-10^8<=ai<=10^8
-10^8<=k<=10^8
样例1：
输入：
n=4
a={1,2,4,7}
k=13
输出：
Yes(13=2+4+7)
样例二：
输入：
n=4
a={1,2,4,7}
k=15
输出：
No
分析：咋一看看确实很难实现：因为从a1开始按顺序决定每一个数加还是不加，这样一来每个数只有两种状态，加和不加。那么最终的算法复杂度就是O（2^n）。
只用普通的算法确实很难实现，但是用上递归问题就迎刃而解了。（ps:下面代码很不规范，命名尽量不要使用中文，我是为了自己好找到以前写的代码才这样做的）
完整代码如下：
package com.renyou.算法;
import java.util.Scanner;
public class 若干数的和为K递归问题 {
private int n,k;
private int[]a;
public static void main(String[] args) {
new 若干数的和为K递归问题().递归();
}
private void 递归() {
Scanner scanner=new Scanner(System.in);
k=scanner.nextInt();//若干数的和
n=scanner.nextInt();//数的个数
a=new int[n];
for(int i=0;i<n;i++){
a[i]=scanner.nextInt();
}
if(dfs(0,0)){
System.out.println("yes");
}else{
System.out.println("no");
}
}
private boolean dfs(int i, int sum) {
if(i==n)return sum==k;
if(dfs(i+1,sum))//不加上a[i]
return true;
if(dfs(i+1,sum+a[i]))//加上a[i]
return true;
return false;
}
}
实例二：雨天积水数量问题。
题干：有一个大小为N*M的园子，雨后积水。八连通的积水被认为是连接在了一起。请求出园子里一共有多少水洼？
（八连通是指下图中相对*的w部分）
wwww*w
www
限制条件：
N，M<=100
输入：
N=5
M=5
园子如下图（w表示积水,*表示没有积水）
**w**
**w**
*****
***w*
**w**
输出：2
分析：
从任意的w开始，不停地把邻接的部分用‘*’代替。1次DFS后与初始的这个w连接的所有w就被替换成了*。因此知道图中没有w了，总共进行了几次的DFS就是积水的个数了。
8个方向对应8种状态转移，所以复杂度是O(8*N*m)=O(n^2)
完整代码如下：
package com.renyou.算法;
import java.util.Random;
import java.util.Scanner;
public class 积水个数的深度优先搜索DFS算法 {
private char[][] field;
private int width,height;
public static void main(String[] args) {
new 积水个数的深度优先搜索DFS算法().solve();
}
private void solve() {
/************ 控制台输入数据 ********************/
Scanner scanner = new Scanner(System.in);
width = scanner.nextInt();
height = scanner.nextInt();
field = new char[width][height];
/************* char数组赋值 ********************/
Random random = new Random();
int num;
for (int i = 0; i < width; i++) {
for (int j = 0; j < height; j++) {
num = random.nextInt(100);
if (num % 5 == 0) {//因为输入太麻烦，自己随机生成
field[i][j] = 'w';
} else {
field[i][j] = '.';
}
}
}
/************ 自动生成field数组元素 *********************/
for (int i = 0; i < width; i++) {
for (int j = 0; j < height; j++) {
System.out.print(field[i][j]);
}
System.out.println();
}
/********* 开始遍历计算field *********/
int res = 0;
for (int i = 0; i < width; i++) {
for (int j = 0; j < height; j++) {
if (field[i][j] == 'w') {
dfs(i, j);
res++;
}
}
}
System.out.println("积水个数" + res);
}
private void dfs(int i, int j) {
field[i][j] = '.';//很重要
for (int dx = -1; dx <= 1; dx++) {
for (int dy = -1; dy <= 1; dy++) {
int nx=i+dx;
int ny=j+dy;
//如果在field内并且有积水继续深度搜索
if(nx>=0&&nx<width&&ny>=0&&ny<height&&field[nx][ny]=='w'){
dfs(nx,ny);
}
}
}
}
}
