假如你落入了一个迷宫，你该如何走出去呢？
尝试走迷宫……
出口
?先向上走走？
?注：图中绿色代表已经经过的地方
出口
?遇到分叉，先走左边试试
出口
?再往下走走试试
出口
?是死路，退回去
出口
?是死路，退回去，往前走走试试
出口
?继续试……
出口
?继续试……
出口
?继续试……
出口
?发现下面的路已经走过了……
?退回去
出口
换个方向走走试试……
出口
换个方向走走试试……
出口
继续试……
出口
继续试……
出口
继续试……
出口
继续试……
出口
继续试……
出口
继续试……
出口
出来了！！
出口
?我们发现，刚刚走迷宫的方法有一个特点，沿着某个方向“一走到底”，如果没有达到目的，就“退回”再沿着另外一个方向
“一走到底”……
?事实上，这就是一个搜索的过程。
DFS深度优先搜索
DepthFirstSearc
深度优先搜索
1.从一个起点（初始状态）开始搜索
2.枚举每一个可能的点（可能的状态）入栈，递归搜索
3.直至到达终点（终止状态），停止递归
DFS的模板
【问题描述】
在一个w×h的矩形广场上，每一块1×1的地面都铺设了红色或黑色的瓷砖。小林同学站在某一块黑色的瓷砖上，他可以从此处出发，移动到上下左右四个相邻的且是黑色的瓷砖上，现在，他想知道，通过重复上述移动所能经过的黑色瓷砖数。
【输入格式】
第1行为h、w，2≤w、h≤50，之间有一个空格隔开。以下为1个w行h列的二维字符矩阵，每个字符为
‘.’‘#’‘@’,分别表示该位置为黑色的瓷砖、红色的瓷砖、小林的初始位置。
【输出格式】
输出一行一个整数，表示小林从初始位置出发可以经过的黑色瓷砖数。
【输入样例】
119
.#.........
.#.#######..#.#.....#..#.#.###.#..#.#..@#.#..#.#####.#..#.......#..#########.
【输出样例】
59
【题目描述】
GeoSurvComp地质探测公司负责探测地下油田。每次GeoSurvComp公司都
是在一块长方形的土地上来探测油田。在探测时，他们把这块土地用网格分成若干个小方块，然后逐个分析每块土地，用探测设备探测地下是否有油田。方块土地底下有油田则称为pocket，如果两个pocket相邻，则认为是同一块油田，油田可能覆盖多个pocket。
你的工作是计算长方形的土地上有多少个不同的油田。
【输入格式】
输入文件中包含多个测试数据，每个测试数据描述了一个网格。每个网格
数据的第一行为两个整数：m、n，分别表示网格的行和列；如果m=0，
则表示输入结束，否则，接下来有m行数据，每行数据有n个字符（不包括行结束符）。每个字符代表一个小方块，如果为*，则代表没有石油，如果为@，则代表有石油，是一个pocket。1≤m≤100，1≤n≤100。
【输出格式】
对输入文件中的每个网格，输出网格中不同的油田数目。如果两块不同的pocket在水平、垂直、或者对角线方向上相邻，则被认为属于同一块油田。每块油田所包含的pocket数目不会超过100.
【输入样例】
35
*@*@*
**@**
*@*@*
55
****@
*@@*@
*@**@
@@@*@
@@**@
00
【输出样例】
1
2
【题目描述】
一矩形阵（n*m）列由数字0到9组成，数字1到9代表细胞，细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞，求给定矩形阵列的细胞个数。
（细胞数字指1到9）
【输入格式】
第一行输入n和m(n,m20)；第二行开始为该矩阵
【输出格式】
一共有的细胞个数。
【输入样例】
410
0234500067
1034560500
2045600671
0000000089
【输出样例】
4
问题：输出{1,2,3……n}的所有排列。
3的全排列
123
132
213
231
312
321
回溯
回溯是搜索算法中的一种控制策略，它的基本思想是：为了求得问题的解，先选择
某一种可能情况向前探索，在探索的过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，直至得到解或者证明无解。
DFS的回溯模板
【问题描述】
已知n(20)个人围着一个圆桌吃饭，其中每一个人都至少认识其他的2个客人。请设计程序求得n个人的一种坐法，使得每个人都认识他左右的