深度优先搜索（DFS）

深度优先搜索（Depth First Search）,又称为回溯法。它从某个状态开始，不断的转移状态，直到无法转移。然后回退到前一步的状态，继续转移到其他状态，如此不断重复，得到最终的解。

举例1：部分和问题
给定整数 a1,a2,a3，…,an判断是否可以从中选中若干数，使他们的和恰好为k.

输入

n = 4;
a= {1,2,3,4}
k=13

输出

Yes {13=2+4+7}

解决方案：

//input
int a[MAX_N];
int n, k;

//已经从前i项得到了和sum ，然后对于i项之后的进行分之。
bool dfs(int i , int sum){
	if(i==n) return sum ==k;//如果前i项都计算过了，则返回sum是否与k相等
    if(dfs(i+1,sum)) return true;//不加上a[i]的情况
	if(dfs(i+1,sum+a[i])) return true;//加上a[i]的情况
	return false;//无论是否加上a[i]都不能凑成k就返回false
}

void solve(){
	if(dfs(0,0)) printf("YES\n");
	else printf("No\n");
	
}

举例2:积水问题
有一个大小为N*M 的园子，雨后积水。八连通的积水被认为是连接在一起的。请求出园子里总共有多少水洼？

输入
N=10， M=12
园子如下图 （‘W’表示积水， ‘.’ 表示没有积水）
w…WW.
.www…WW.
…w…w…
…w…
…
…
…w…
.ww…
…
…
输出
3

解题思路： 从任意的w开始。不停地把邻接的部分用’.'代替。 1次DFS后与初始的这个w连接的所有w就都被替换成‘.’ , 因此直到图中不存在w 为止。总共进行DFS的次数就是答案，8个方向共对应了8种状态转移，每个格子作为DFS的参数至多被调用一次，所以复杂度为O（8NM）= O（N*M）。

//输入
int N, M;
char field[MAX_N][MAX_M+1]; //园子

//现在位置（x,y）
void dfs(int x, int y){
	//将现在的位置替换为.
	field[x][y] = '.';
	
	//循环遍历易懂的8个方向
	for(int dx = -1; dx <= 1; dx++){
		for(int dy = -1; dy <= 1; dy++){
			//	向x方向移动dx, 向y方向移动dy，移动结果为（nx,ny）
			int nx = x+dx, ny = y+dy;
			//判断（nx,ny）是不是在园子里，以及是否有积水
			if(0 <= nx &&  nx < N && 0 <=ny && ny < M && field[nx][ny] =='w'){
				dfs(nx,ny);
			}
		}
	}
	return ;
}

void solve(){
	int res = 0;
	for(int i = 0; i < N; i++){
		for(int j = 0; j < M; j++){
			if(field[i][j] == 'w'){
				//从有w的地方开始dfs
				dfs(i,j);
				res++;		
			}
		
		}
	

	}
	printf("%d\n",res);


}

引用
[1] 挑战程序设计竞赛（第2版）