C++ 算法篇 深度优先搜索（DFS）
深度优先搜索
深度优先搜索是将当前状态按照一定的规则顺序，先拓展一步得到一个新状态，再对这个新状态递归拓展下去。如果无法拓展，则退回一步到上一个状态，再按照原先设定的规则顺序重新寻找一个状态拓展。如此搜索，直至找到目标状态，或者遍历完所有状态。所以，深度优先搜索也是一种“盲目”搜索。
图9.10-1所示的一个“无向图”，从顶点V0开始进行深度优先搜索，得到的一个序列为：V0，V1，V2，V6，V5，V3，V4。
一、深度优先搜索的算法框架
深度优先搜索（Depth First Search，DFS），简称深搜，其状态“退回一步”的顺序符合“后进先出”的特点，所以采用“栈”存储状态。深搜适用于要求所有解方案的题目。
深搜可以采用直接递归的方法实现，其算法框架如下
二、 深度优先搜索应用举例
1、瓷砖
【问题描述】
在一个 w×h 的矩形广场上，每一块 1×1 的地面都铺设了红色或黑色的瓷砖。小林同学站在某一块黑色的瓷砖上，他可以从此处出发，移动到上、下、左、右四个相邻的且是黑色的瓷砖上。现在，他想知道，通过重复上述移动所能经过的黑色瓷砖数。
【输入格式】
第 1 行为 h、w，2≤w、h≤50，之间由一个空格隔开。
以下为一个 w 行 h 列的二维字符矩阵，每个字符为“.”“#”“@”，分别表示该位置为黑色的瓷砖、红色的瓷砖，以及小林的初始位置。
【输出格式】
输出一行一个整数，表示小林从初始位置出发可以到达的瓷砖数。
【输入输出样例】
11 9
.#.........
.#.#######.
.#.#.....#.
.#.#.###.#.
.#.#..@#.#.
.#.#####.#.
.#.......#.
.#########.
...........
【问题分析】
设 ans 表示小林从初始位置出发可以经过的黑色瓷砖数，初始值为 0，从小林的初始位置“@”开始深度优先搜索，ans++，再把该位置设置为红色（已走过），然后穷举其上、下、左、右四个位置是否是黑色瓷砖。是，则递归搜索。
2、 最大黑区域
【问题描述】
二值图像是由黑白两种像素组成的矩形点阵，图像识别的一个操作是求出图像中最大黑区域的面积。请设计一个程序完成二值图像的这个操作。黑区域由黑像素组成，一个黑区域中的每像素至少与该区域中的另一像素相邻，规定一个像素仅与其上、下、左、右的像素相邻。两个不同的黑区域没有相邻的像素。一个黑区域的面积是其所包含的像素数。
【输入格式】
第 1 行含两个正整数 n 和 m，1≤n、m≤100，分别表示二值图像的行数与列数，后面紧跟着n 行，每行含 m 个整数 0 或 1，其中第 i 行表示图像的第 i 行的 m 个像素，0 表示白像素，1 表示黑像素。
【输出格式】
输出一个数，表示相应的图像中最大黑区域的面积。
【输入样例】
5 6
0 1 1 0 0 1
1 1 0 1 0 1
0 1 0 0 1 0
0 0 0 1 1 1
1 0 1 1 1 0
【输出样例】
7
【问题分析】
从左上角开始，利用一个两重循环穷举找到一个黑点（a［i，j］=1），然后 dfs（i，j），dfs 到的点置为 0，一次 dfs 完毕得到一个返回值 s，就是这个黑区域的面积，再通过打擂台，记录每一个黑区域的 s 最大值作为答案 ans。
3、数的拆分
【问题描述】
输入一个整数 n，输出 n 拆分成若干正整数和的所有方案，即 n=S 1 +S 2 +…+S k 的形式，且S 1 ≤S 2 ≤…≤S k ，n≤20，请按照字典序输出。
【输入格式】
一行一个整数 n。
【输出格式】
所有拆分方案，具体格式参见输出样例。
【输入样例】
4
【输出样例】
1+1+1+1
1+1+2
1+3
2+2
4
total=5
【问题分析】
分析对比 5 的拆分和 4