搜索是计算机程序设计中一种最基本、最常用的算法。搜索算法是直接基于计算机高速运算的 特点而使用的计算机求解方法。 它是从问题的初始状态出发，根据其中的约束条件，按照一定的策略，有序推进，不断深入， 对于达到的所有目标状态（解空间），一一验证，找到符合条件的解（可行解），或者找出所 有可行解中的最优解。
深度优先搜索是将当前状态按照一定的规则顺序，先拓展一步得到一个新状态， 再对这个新状态递归拓展下去。如果无法拓展，则退回一步到上一个状态，再按 照原先设定的规则顺序重新寻找一个状态拓展。如此搜索，直至找到目标状态， 或者遍历完所有状态。所以，深度优先搜索也是一种“盲目”搜索。 对于图9.10-1所示的一个“无向图”，从顶点V0开始进行深度优先搜索， 得到的一个序列为：V0，V1，V2，V6，V5，V3，V4
深度优先搜索（Depth First Search，DFS），简称深搜， 其状态“退回一步”的顺序符合“后进先出”的特点， 所以采用“栈”存储状态。深搜适用于要求所有解方案的题目。 深搜可以采用直接递归的方法实现，其算法框架如下：
void dfs(int dep, 参数表 );{ 自定义参数 ; if( 当前是目标状态 ){ 输出解或者作计数、评价处理 ; }else for(i = 1; i <= 状态的拓展可能数 ; i++) if( 第 i 种状态拓展可行 ){ 维护自定义参数 ; dfs(dep+1, 参数表 ); } }题目描述
在国际象棋棋盘上（8*8）放置八个皇后，使得任意两个皇后之间不能在同一行，同一列，也不能位于同于对角线上。问共有多少种不同的方法，并且按字典序从小到大指出各种不同的放法。
输入格式
无
输出格式
1 5 8 6 3 7 2 4 1 6 8 3 7 4 2 5 … 总方法数
样例
样例输入 无 样例输出 1 5 8 6 3 7 2 4 1 6 8 3 7 4 2 5 … 92
解题思想 用深搜模拟当前棋盘上皇后的位置，判断当前位置可不可以放下皇后 若可以，储存下皇后的纵坐标，当8个皇后放完之后开始下一轮模拟， 直到找到最后一种解
代码实现
#include<cmath> #include<cstdio> int n,i,a[101],sum,w[101][10],j; bool judge(int N) { for(int j=1;j<N;j++) { if(abs(a[j]-a[N])==abs(j-N)||a[j]==a[N]) { return false; } } return true; } void save() { sum++; for(int j=1;j<=n;j++) { w[sum][j]=a[j]; } } void solve(int i) { if(i>n) { save(); return ; } for(int j=1;j<=n;j++) { a[i]=j; if(judge(i)) { solve(i+1); } } } int main() { n=8; solve(1); for(i=1;i<=sum;i++) { for(j=1;j<=8;j++) { printf("%d ",w[i][j]); } printf("\n"); } printf("%d",sum); }题目描述
会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有 8 * 8 个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。对于某个满足要求的 8 皇后的摆放方法，定义一个皇后串 a 与之对应，即 a=b1b2…b8，其中 bi 为相应摆法中第 i 行皇后所处的列数。已经知道 8 皇后问题一共有 92 组解（即92个不同的皇后串）。 给出一个数 b，要求输出第 b 个串。串的比较是这样的：皇后串 x 置于皇后串 y 之前，当且仅当将 x 视为整数时比 y 小。
输入格式
第 1 行是测试数据的组数 n，后面跟着 n 行输入。每组测试数据占 1 行，包括一个正整数 b(1 <= b <= 92)。
输出格式
输出有 n 行，每行输出对应一个输入。输出应是一个正整数，是对应于 b 的皇后串。
样例
输入样例 2 1 92 输出样例 15863724 84136275
解题思想 利用上一题将所有皇后模拟出来的数组 直接打印对应组号就可以A掉
代码实现
#include<cmath> #include<cstdio> int n,i,a[101],sum,w[101][10],j,num,t; bool judge(int N) { for(int j=1;j<N;j++) { if(abs(a[j]-a[N])==abs(j-N)||a[j]==a[N]) { return false; } } return true; } void save() { sum++; for(int j=1;j<=n;j++) { w[sum][j]=a[j]; } } void solve(int i) { if(i>n) { save(); return ; } for(int j=1;j<=n;j++) { a[i]=j; if(judge(i)) { solve(i+1); } } } int main() { n=8; solve(1); scanf("%d",&num); while(num--) { scanf("%d",&t); for(i=1;i<=8;i++) printf("%d",w[t][i]); printf("\n"); } }题目描述
从三个元素的集合[A，B，C]中选取元素生成一个 N 个字符组成的序列，使得没有两个相邻的子序列（子序列长度=2）相同。例：N = 5 时 ABCBA 是合格的，而序列 ABCBC 与 ABABC 是不合格的，因为其中子序列 BC，AB 是相同的。 对于由键盘输入的 N(1<=N<=12)，求出满足条件的 N 个字符的所有序列和其总数。
输入格式
一个N(1<=N<=12)
输出格式
求出满足条件的 N 个字符的所有序列和其总数。
样例
输入样例 4 输出样例 72
解题思想 依旧靠模拟现在数组中的元素并且判断相邻两个 元素构成的子序列是否是满足条件的解，是就进行 计数并搜索下一层
代码实现
#include<cstdio> #define ll long long ll a[1000005],n,sum; bool check(int p) { return p>3&&a[p-3]*10+a[p-2]==a[p-1]*10+a[p]; } void dfs(int p) { ll i;//要每次都重新定义i的变量，不然在调用的时候会改变外层搜索的i变量 for(i=1;i<=3;i++) { a[p]=i; if(check(p))//只用判断相邻的字符串，之前的是因为判断了所有的情况 continue; else { if(p==n) sum++; else dfs(p+1); } } } int main() { scanf("%lld",&n); dfs(1); printf("%lld",sum); }题目描述
任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和。 当n=7共14种拆分方法： 7=1+1+1+1+1+1+1 7=1+1+1+1+1+2 7=1+1+1+1+3 7=1+1+1+2+2 7=1+1+1+4 7=1+1+2+3 7=1+1+5 7=1+2+2+2 7=1+2+4 7=1+3+3 7=1+6 7=2+2+3 7=2+5 7=3+4
输入格式
输入n。
输出格式
按字典序输出具体的方案。
样例
输入样例 7 输出样例 1+1+1+1+1+1+1 1+1+1+1+1+2 1+1+1+1+3 1+1+1+2+2 1+1+1+4 1+1+2+3 1+1+5 1+2+2+2 1+2+4 1+3+3 1+6 2+2+3 2+5 3+4
解题思想 在DFS函数中传入当前递归层数，记录当前分解的值 并搜索下一层
代码实现
#include<cstdio> int a[1005]={1},n; int print(int t) { int i; for(i=1;i<t-1;i++) printf("%d+",a[i]); if(a[t-1]!=n) printf("%d\n",a[t-1]); } int search(int s,int t) { int i; if(s==0) print(t); for(i=a[t-1];i<=s;i++) { a[t]=i; search(s-i,t+1); } } int main() { scanf("%d",&n); search(n,1); }题目描述
输入自然数N，然后将其拆分成由若干数相加的形式，参与加法运算的数可以重复。
输入格式
第1行：1个整数n(n≤30)
输出格式
所有拆分方案，顺序见样例。
样例
输入样例 4 输出样例 1+3 1+1+2 1+1+1+1 2+2
解题思想 在DFS函数中传入当前递归层数，记录当前分解的值 并搜索下一层，不过因为a[i]<=a[i+1],所以循环只调用 n的一半
代码实现
#include<cstdio> int a[100005]={1},n; void print(int d) { if(d>=2) { int i; for(i=1;i<d-1;i++) printf("%d+",a[i]); printf("%d\n",a[d-1]); } } void DFS(int d,int x) { int i; for(i=a[d-1];i<=x/2;i++) { a[d]=i; d++; a[d]=x-i; print(d+1); DFS(d,a[d]); d--; } } int main() { scanf("%d",&n); DFS(1,n); }“回溯法”也称“试探法”。它是从问题的某一状态出发，不断“试探”着往前走一步，当一条路走到“尽头”，不能再前进（拓展出新状态）的时候，再倒回一步或者若干步，从另一种可能的状态出发，继续搜索，直到所有的“路径（状态）”都一一试探过。这种不断前进、不断回溯，寻找解的方法，称为“回溯法”。 深度优先搜索求解的时候，当找到目标结点之后，还要回头寻找初始结点到目标结点的解路径。而回溯法则不同，找到目标结点之后，搜索路径就是一条从初始结点到目标结点的解路径。回溯法实际上是状态空间搜索中，深度优先搜索的一种改进，是更实用的一种搜索求解方法。
或者
void search(dep:integer){ 自定义参数 ; for(i = 1;i <= 状态的拓展可能数 ;i++) if( 第 i 种状态拓展可行 ){ 保存现场 ( 断点 ), 维护自定义参数 ; if( 当前是目标状态 ){ 输出解或者作计数和评价处理 ; }else search(dep+1); 恢复现场 , 回溯到上一个断点继续执行 ; } }1）深度优先搜索包含回溯，或者说回溯法是深度优先搜索的一种。 2）深度优先搜索需要控制如何实现状态之间的转移（拓展），回溯法就是深度优先搜索的一种控制策略。 3）回溯的过程中，并不需要记录整棵“搜索树”，而只需记录从初始状态到当前状态的一条搜索路径，是“线性链状”的，其最大优点是占用空间少。 4）深度优先搜索可以采用递归（系统栈）和非递归（手工栈）两种方法实现。递归搜索是系统栈实现一部分的回溯（如果需要记录一些特殊信息或较多的信息，还需要另外手工记录），而非递归是自己用手工栈模拟回溯的过程，所以实现起来略为复杂一点。
题目描述
输入 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
解题思想
直接按当前状态一直分解下去，直到分解完全 之后再回溯上一步与深度优先搜索的方法类似，从 dep=1 开始，每次 dfs（dep）先拆出一个数 i，记录下来，并且修改余数 rest=rest-i，然后 dfs（dep+1）去递归拆分下去，只是每次递归结束后需要做回溯操作，即 rest=rest+i。
代码实现（核心）
void dfs(int dep){ if(rest == 0) pr(dep-1); else for(int i = s[dep-1]; i <= rest; i++){ s[dep] = i; rest -= i; dfs(dep+1); rest += i; } }题目描述
设有 n 个整数的集合 {1，2，3，…，n}，从中取出任意 r 个数进行排列（0<r<n<20），编程输出所有的排列方案。请按照字典序输出。
输入格式
一行两个整数 n 和 r，之间用一个空格隔开。
输出格式
所有排列方案，具体格式参见输出样例。
样例
输入样例 4 2 输出样例 1 2 1 3 1 4 2 1 2 3 2 4 3 1 3 2 3 4 4 1 4 2 4 3 total=12
解题思想 【问题分析】
复述一下题意就是：r 个位置，每个位置放一个 1~n 之间的整数，要求每个数不能重复，输出所有的排列方案。 可以从第 1 个位置开始，每个位置放置数 k，k 从 1 开始不断尝试直到 n，如果能放（没用过）就放，放好后再尝试下一个位置，如果第 r 个位置也放好了，则说明一种方案已经形成，则输出一种方案、计数，继续寻找下一种方案（回溯）。如果不能放置（该数已用过）就换放下一个数，如果 k大于 n 了，表示不能继续放下去了，则回溯。一个数有没有用过，只要开一个哈希表判断即可
代码实现（核心）
略，自己写题目描述
要在 N×N（N≤8）的国际象棋棋盘中放 N 个皇后，使得任意两个皇后都不能互相吃（提示：皇后能吃同一行、同一列、同一对角线的其他皇后）。 请问有多少种方案，并按字典序输出所有的方案。每种方案输出每一行皇后的纵坐标（场宽为 5），如果无解，则输出“no solute!”。
输入格式
一个N(1<=N<=12)
输出格式
每行对应一种方案，具体格式参见输出样例。
样例
输入样例 4 输出样例 2 4 1 3 3 1 4 2
解题思想 无 代码实现
#include<cmath> #include<cstdio> int n,i,a[101],sum,w[101][10],j; bool judge(int N) { for(int j=1;j<N;j++) { if(abs(a[j]-a[N])==abs(j-N)||a[j]==a[N]) { return false; } } return true; } void save() { sum++; for(int j=1;j<=n;j++) { w[sum][j]=a[j]; } } void solve(int i) { if(i>n) { save(); return ; } for(int j=1;j<=n;j++) { a[i]=j; if(judge(i)) { solve(i+1); } } } int main() { scanf("%d",&n); solve(1); for(i=1;i<=sum;i++) { for(j=1;j<=n;j++) { printf("%d ",w[i][j]); } printf("\n"); } }宽度优先搜索（Breadth First Search，BFS），简称宽搜，又称广度优先搜索。它是从初始结点开始，应用产生式规则和控制策略生成第一层结点，同时检查目标结点是否在这些生成的结点中。若没有，再用产生式规则将所有第一层结点逐一拓展，得到第二层结点，并逐一检查第二层结点是否包含目标结点。若没有，再用产生式规则拓展第二层结点。如此依次拓展，检查下去，直至发现目标结点为止。如果拓展完所有结点，都没有发现目标结点，则问题无解。 对于以上“无向图”，从顶点 V0 开始进行宽度优先搜索，得到的一个序列为 V0，V1，V2，V3，V4，V6，V5。 宽度优先搜索是一种“盲目”搜索，所有结点的拓展都遵循“先进先出”的原则，所以采用“队列”来存储这些状态。宽度优先搜索的算法框架如下：
题目描述
在一个 w×h 的矩形广场上，每一块 1×1 的地面都铺设了红色或黑色的瓷砖。小林同学站在某一块黑色的瓷砖上，他可以从此处出发，移动到上、下、左、右四个相邻的且是黑色的瓷砖上。现在，他想知道，通过重复上述移动所能经过的黑色瓷砖数。
输入格式
第 1 行为 h、w，2≤w、h≤50，之间由一个空格隔开； 以下为一个 w 行 h 列的二维字符矩阵，每个字符为“.”“#”“@”，分别表示该位置为黑色的瓷砖、红色的瓷砖、小林的初始位置。
输出格式
输出一行一个整数，表示小林从初始位置出发经过的黑色瓷砖数。
样例
样例输入 11 9 . # . . . . . . . . . . # . # # # # # # # . . # . # . . . . . # . . # . # . # # # . # . . # . # . . @ # . # . . # . # # # # # . # . . # . . . . . . . # . . # # # # # # # # # . . . . . . . . . . . . 样例输出 59
解题思想 【问题分析】 读入字符数组，找到小林的初始位置“@”，并把坐标入队，作为队头元素。宽度优先搜索，检查队头元素的上、下、左、右四个位置是否是黑色瓷砖“.”，是则入队，……不断取出队头元素进行四个方向的拓展，直到队列为空。 为了避免一个位置被多次重复走到，定义一个布尔型数组 a[i,j]用来判重，位置（i，j）为黑色瓷砖设置为 true，红色的或者走过的瓷砖设置为 false。 最后，队列的尾指针即为答案。本题是搜索的一个重要应用，所谓的求“联通块”问题。
代码实现
自己加油题目描述
二值图像是由黑和白两种像素组成的矩形点阵，图像识别的一个操作是求出图像中最大黑区域的面积。请设计一个程序完成二值图像的这个操作。黑区域由黑像素组成，一个黑区域中的每像素至少与该区域中的另一像素相邻，规定一个像素仅与其上、下、左、右的像素相邻。两个不同的黑区域没有相邻的像素。一个黑区域的面积是其所包含的像素数。
输入格式
第 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
解题思想 【问题分析】 如果先找到一个黑点，那么问题就和例 2 一样了。所以，本题只要从左上角开始，利用一个两重循环穷举找到一个黑点（a［i，j］=1），然后做一遍宽搜，并且记下此黑色区域（联通块）的大小，再通过打擂台记录最大值作为答案 ans。如果题目要求的是有几个黑区域，则只要每次宽搜时“计数器”加一。
代码实现
Fighting！题目描述
在一片广阔的土地上有一个鸟人，他需要从这里穿过原野回到基地。这片原野上有平地（P）、有湖泊（L）。因为鸟人可以飞，所以有的时候，他可以飞越湖泊。现在，鸟人需要用最快的时间回到基地。 假设原野是一个 m×n 的矩阵，有两种地形，用 P 和 L 表示。鸟人只能停留在平地上。他目前处在（1，1）这个位置，而目的地是（m，n）。他可以向上、下、左、右四个方向移动，或者飞行。 每移动一格需要 1 个单位时间。而飞行无论飞多远，都只需要 1 个单位时间。飞行的途中不可以改变方向。也就是说，飞行也只能是上、下、左、右四个方向，并且一次飞行最终必须降落在平地上。当然，受到能量的限制，鸟人不能无限制地飞行，他总共最多可以飞行的距离为 D。
输入格式
第 1 行是 3 个整数 m、n 和 D，3 个数都不超过 100。 下面是一个 m×n 的字符矩阵，表示原野。
输出格式
输出一行一个整数表示最短时间。如果无法到达，输出“impossible”。
样例
输入样例 4 4 2 PLLP PPLP PPPP PLLP 输出样例 5
题目描述
有 n 个人，编号为 1~n。其中有一些人相互认识，现在 x 想要认识 y，可以通过他所认识的人来认识更多的人（如果 a 认识 b、b 认识 c，那么 a 可以通过 b 来认识 c），求出 x 最少需要通过多少人才能认识 y。
输入格式
第 1 行 3 个正整数 n、x、y，其中：n≤100，1≤x、y≤n。 接下来是一个 n×n 的邻接矩阵，a[i,j]=1 表示 i 认识 j，a[i,j]=0 表示 i 不认识 j。 保证 i=j 时，a[i,j]=0，并且 a[i,j] =a[j,i]，一行中的两个数之间有一个空格。
输出格式
输出一行一个数，表示 x 认识 y 最少需要通过的人数。
样例
输入样例 5 1 5 0 1 0 0 0 1 0 1 1 0 0 1 0 1 0 0 1 1 0 1 0 0 0 1 0 输出样例 2
解题思想
本题是宽度优先搜索的一个重要应用“求最优值问题”。先设答案 ans=0。把 x 加入队列并设置为队头元素，从队头开始进行宽搜，穷举邻接矩阵的第 x 行，看 x 认识谁（判断 a[x,j]=1），认识的人（j）全部依次入队，并且 ans++，如果出现了 y，则输出 ans，结束搜索，否则，取出队头元素继续宽搜。
代码实现
由于作者太过懒惰，没有诶若各位D神有例题的Ac代码或问题代码 都可在评论区留言，大家共同探讨学习 也便于本博客的完善！！谢谢大家！！
