dfs各大题目类型

1.遍历各个位置，并且记录每组遍历的路程

遍历各个位置的时候就在每个dfs（u）里遍历下一个dfs（u+1）。

记录路程用数组。

如果要求每个数只能用一次或者每个点只能走一次的话用一个bool或int数组来储存他的状态（遍历过或没遍历过）

如果问题有边界的情况，如给你了n个位置，或者是n*n的图我们遍历每一行的话，递归的出口就是当我们那层的数等于n，如果一个位置有多种情况（如能填多个数）的话，我们需要回溯操作的时候，先在dfs之前把状态修改，在dfs之后把状态复原。

例题1：n个数的全排列

题目：输入n，输出1-n的全排列

思路：我们可以按照位置编号一个一个搜，从0编号开始搜，递归的出口是这个位置的编号==n，而且在这个时候我们就可以输出记录路径的数组里存的数，然后我们再枚举从1到n的数，如果他没有被遍历的话我们就把这个数放到这个位置，修改这个数的状态和位置上的数，dfs他的下一个位置，当dfs递归出来之后我们需要把这个数的状态和这个位置的数恢复到原来的样子 。

代码实现如下：

#include
#include
#include
#include
using namespace std;

bool st[105];//用来储存每个数的状态
int path[105];//用来记录每个位置所存的数
int n;
void dfs(int u){
	if(u==n){
		for(int i=0;i>n;
	dfs(0);//从0这个位置开始搜
	
	return 0;
}

 当然，我们要实现全排列的话，algorithm里有一个专门用来全排列的函数next_permutation:

他的作用是输出这个序列的下一个序列，如果没有下一个序列就返回0。那么我们可以先把一个数组从小到大排序之后保证这个是字典序最小的排列，然后我们用这个函数即可。

代码：

#include
#include
#include
using namespace std;

int a[105];
int n;
int main(){
	cin>>n;
	for(int i=0;i 
当然这个函数是按升序的全排列，还有一个prev_permutation函数是输出这个序列的上一个序列，所以我们先把他按从大到小的顺序把这个序列排序，保证他是最大的序列，然后用prev_permutation即可。（代码略）
 
例子2：n皇后问题
 
n−n−皇后问题是指将 nn 个皇后放在 n×nn×n 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。
 
 
现在给定整数 nn，请你输出所有的满足条件的棋子摆法。
 
输入格式
 
共一行，包含整数 n。
 
输出格式
 
每个解决方案占 n 行，每行输出一个长度为 n 的字符串，用来表示完整的棋盘状态。
 
其中 . 表示某一个位置的方格状态为空，Q 表示某一个位置的方格上摆着皇后。
 
每个方案输出完成后，输出一个空行。
 
注意：行末不能有多余空格。
 
输出方案的顺序任意，只要不重复且没有遗漏即可。
 
数据范围
 
1≤n≤91≤n≤9
 
输入样例：
 
4
 
输出样例：
 
.Q..
...Q
Q...
..Q.

..Q.
Q...
...Q
.Q..
 
 思路：
 
方法1：我们可以按照每行的皇后应该放哪一列来搜，dfs的是行数，从第0行开始搜，当到第n行的时候我们就可以输出整个图。题目的要求是同一行同一列同一个对角线不能有皇后，所以我们可以开三个bool数组分别表示第i列有无皇后，对角线i有无皇后和反对角线有没有皇后，当每次搜到每一行时我们要判断对应的列数对角线数反对角线的地方有没有皇后，如果没有我们更改他的状态然后再搜他的下一行。
 
#include
#include
#include
using namespace std;
const int N=105;
int n;
char g[N][N];
bool col[N],ug[N],dug[N];//分别表示对应的列和对角线反对角线上有没有皇后的状态
void dfs(int u){
	if(u==n){
		for(int i=0;i>n;
	for(int i=0;i 
 方法2：我们可以直接从00开始一个位置一个位置往下搜，开四个bool数组分别表示行列对角线反对角线的状态。每个位置我们有放和不放两个选择，当放的时候递归到下一层我们就把当前皇后数++，x不动，y++就可，当不放的时候我们的皇后数不变。递归的出口是x==n，当皇后数==n的时候我们就能输出这个图，否则不输出。
 
#include
#include
#include
using namespace std;
const int N=105;
char g[N][N];
int col[N],row[N],ug[N],dug[N];
int n;
void dfs(int x,int y,int s){
	if(y==n){
		y=0;
		x++;
	}
	if(x==n){
		if(s==n){
			for(int i=0;i>n;
	for(int i=0;i 
第二种：把所有点都遍历，搜符合要求的点（根据题意搜符合要求的点的话就不用再去设置递归出口了）
 
例子1：A - Oil Deposits（石油储藏）
 
GeoSurvComp地质勘测公司负责探测地下石油储藏。GeoSurvComp一次处理一大片矩形土地，并创建一个网格，将土地分成许多方形地块。然后，它分别分析每一个地块，使用传感设备来确定该地块是否含有石油。含有石油的地块被称为“口袋”。如果两个气穴相邻，那么它们是同一个油藏的一部分。石油储量可能相当大，并可能包含许多口袋。你的工作是确定一个网格中包含多少不同的石油储量。
 
投入
 
输入包含一个或多个格网。每个网格以包含m和n的一行开始，m和n是网格中的行数和列数，由一个空格分隔。如果m = 0，则表示输入结束；否则1 <= m <= 100且1 <= n <= 100。接下来是m行，每行n个字符(不包括行尾字符)。每个字符对应一个图，或者是`* '，代表没有油，或者是`@ '，代表一个油包。
  
 
输出
 
水平、垂直或对角相邻。一个油矿不会包含超过100个矿坑。
 
样品
 
投入copy
输出复制
 
1 1
*
3 5
*@*@*
**@**
*@*@*
1 8
@@****@*
5 5 
****@
*@@*@
*@**@
@@@*@
@@**@
0 0
 
 
0
1
2
2
 
思路：每次输入图之后遍历每个点，如果符合要求的话总数就++（作用是在第一个搜索点的时候统计数量，再搜这个点附近的符合要求的点的时候我们就不用加了，因为是一块油井），把这个点改成没有油的地方标识一下已经被搜过，（不用恢复状态是因为搜完之后就不用再搜了）然后搜这个点以中心的九宫格有没有符合要求的点，有的话就搜他。
 
#include
#include
#include
using namespace std;
const int N=200;
char g[N][N];
int ans;
int m,n;
bool qs(int x,int y){
	if(x>=0&&x=0&&y>m>>n;
		if(m==0)break;
		for(int i=0;i>g[i][j];
			}
		}
		ans=0;
		for(int i=0;i 
  例子2：单词接龙
 
单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如 beast和 astonish，如果接成一条龙则变为 beastonish ，另外相邻的两部分不能存在包含关系，例如 at 和 atide 间不能相连。
 
输入格式 
输入的第一行为一个单独的整数 n (n le 20)n(n≤20) 表示单词数，以下 nn 行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在。
 
输出格式 
只需输出以此字母开头的最长的“龙”的长度。
 
样例说明 
连成的“龙”为 atoucheatactactouchoose
 
Sample 1
 
Inputcopy
Outputcopy
 
5
at
touch
cheat
choose
tact
a
 
 
23
 
思路：这个思路就是搜以d为头的字符串和其他字符串有没有重合的字符，当搜到d的话长度更新然后d使用的次数++，如果有的重合的字符话我们再更新他的长度之后搜那个跟d有重复字符的字符串。
 
用一个string数组来储存输入的数，一个int数组记录一个单词被用了几次（最多只能用两次，当头当尾），然后用一个二维数组来记录两个字符串的重合字符的长度。
 
#include
#include
#include
using namespace std;
const int N=200;
string a[N];//记录读入的单词
int g[N][N];//记录以字符串i为前面j为后面的两个字符重叠的长度
int ans;
int n;
int use[N];//记录每个单词使用的次数（每个单词可以用两次，所以当他小于2的时候就可以用
void dfs(string d,int last){//搜以d为前面的字符，i为前面字符编号
	int t=d.size();
	ans=max(ans,t);//更新长度
	use[last]++;//他的使用次数++
	for(int i=1;i<=n;i++){//遍历字符串，如果和d有重合部分且他的使用次数小于2就能用
		if(g[last][i]&&use[i]<2){
			dfs(d+a[i].substr(g[last][i]),i);//传入改变之后把后面的字符脸上的字符串，传入后面字符串的编号
		}
	}
	use[last]--;//当出来的时候要回溯，（因为可能有好几个以op开头的字符串，所以我们搜完之后要把搜过的恢复以免影响下次搜索
	
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	char op;
	cin>>op;
	for(int i=1;i<=n;i++){//先算两个单词重叠的长度
		for(int j=1;j<=n;j++){
			string q1=a[i];
			string q2=a[j];
			for(int k=1;k 
3.记忆化搜索：当点搜过就返回这个点的数据，如果没被搜过就继续搜
 
例：滑雪
 
Michael喜欢滑雪百这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子
 
 1  2  3  4 5

16 17 18 19 6

15 24 25 20 7

14 23 22 21 8

13 12 11 10 9
 

 一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上，这是最长的一条。
 
Input
 
输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行，每行有C个整数，代表高度h，0<=h<=10000。
 
Output
 
输出最长区域的长度。
 
Sample
 
Inputcopy
Outputcopy
 
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
 
 
25
 
 思路：读入高度之后，设置一个二维数组f[i][j]数组来表示以i，j点为起点的所有路径的最大长度，并先初始化为-1，那么i，j这个点的最大长度就是他的左右前后点为起点的最大长度+1取max，而且我们要注意，f最小为1，当这个点不是-1时说明已经算出来过了直接返回，如果是-1我们就开始搜他的前后左右，注意搜的时候要判断他的前后左右的点的高度是否小于他，小于才能执行。
 
#include
#include
#include
using namespace std;

int r,c;
const int N=110;
int h[N][N];//记录高度
int f[N][N];//记录以ij为起点的路径的最大长度
int ans;
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
int dfs(int x,int y){
	if(f[x][y]!=-1)return f[x][y];//当被算过就返回
	f[x][y]=1;//最小为1（只有本身一格
	for(int i=0;i<4;i++){//然后遍历他的前后左右，如果满足低于他的高度就比较取max
		int x1=x+dx[i];
		int y1=y+dy[i];
		if(x1>=1&&x1<=r&&y1>=1&&y1<=c&&h[x][y]>h[x1][y1]){
			f[x][y]=max(f[x][y],dfs(x1,y1)+1);
		}
	}
	return f[x][y];
}
int main(){
	cin>>r>>c;
	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++){
			cin>>h[i][j];
		}
	}
	ans=0;
	memset(f,-1,sizeof f);
	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++){
			ans=max(ans,dfs(i,j));
		}
	}
	cout<