机试搜索----dfs
图的存储：链式前向星法：背下这个模板很重要；
重点：dfs模板+add()函数加边的方法（无向图则要加两次） ///利用的链表法的思想
主要理解：
1.函数 add() 作用加边（链式前向星法）本质是数组模拟链表 进行前插法加入元素
h[ ] 是表头指针 、e[ ] 存放边的终点、ne[ ]存放下一条边的索引
加边的逻辑 : 新边插在表头，idx自增分配新边
void add(int a,int b){ e[idx] = b; ne[idx] = h[a]; h[a]=idx++; }//a为前驱，b为所指向的节点 //e[]为边集数组 //h[]为表头数组 //idx为边的编号 //初始时使用memset(h,-1,sizeof h);将表头数组内的值为-1，初始化2.dfs函数（）
dfs模板 ：
u 当前遍历节点， fa为当前父节点
for 循环 表示：从节点u的第一条边开始遍历，直至i = -1 结束
i = ne[i] 表示沿着链表下一条边遍历
void dfs(int u,int fa){ for(int i = h[u];~i;i=ne[i]){//~i 相当于 i！= -1 int j = e[i]; if(j==fa) continue;//如果与父节点一样，则跳过 // 题意计算过程 // dfs(j,u);//再次递归 } }题目1.求树高度///注意如果有超时错误，则把cin和cout改为scanf和printf，这两个两者效率高
#include<bits/stdc++.h> using namespace std; const int N =10010,M=2*N; int h[N],e[M],ne[M],idx; int dist[N]; int n,m; int res; void add(int a,int b){ e[idx] = b,ne[idx]=h[a],h[a]= idx++; //链式前向星法 } void dfs(int u,int fa){ for(int i = h[u];~i;i=ne[i]){//下条边为 i= ne[i] int j = e[i]; if(j==fa) continue; dist[j] = dist[u]+1; res = max(res,dist[j]); dfs(j,u); } } int main(){ memset(h,-1,sizeof h); scanf("%d %d",&n,&m); for(int i=0;i<n-1;i++){//构建边为 n-1条 int a,b; scanf("%d %d",&a,&b); add(a,b),add(b,a); } memset(dist,0,sizeof dist);//初始化dist数组 dfs(m,-1); printf("%d",res); return 0; }2.雅码人的密码3385. 玛雅人的密码 - AcWing题库
思路：借用队列和map容器两种数据结构，map进行存放字符串以及距离
#include<bits/stdc++.h> using namespace std; int main(){ int n; scanf("%d",&n); if(n<4){ cout<<"-1"<<endl; return 0; } char strArr[20]= {0};//初始化 scanf("%s",strArr); string str = strArr; queue<string> tovisit;//队列 tovisit.push(str);//入队 unordered_map<string,int> distance;//map存放数组 distance.insert({str,0});//初始map while(tovisit.empty()==false){//循环条件 string cur = tovisit.front(); if(cur.find("2012")!=string::npos){//不为空，string::npos判空条件 printf("%d",distance[cur]); break; } tovisit.pop(); for(int i = 0;i<cur.size()-1;i++){//对字符串的每个字母进行对换 string next = cur; swap(next[i],next[i+1]); if(distance.count(next)==0){ tovisit.push(next); distance.insert({next,distance[cur]+1}); } } } if(tovisit.empty()==true) printf("-1"); return 0; }3.P1605 迷宫 - 洛谷 dfs+回溯
思路：利用dfs的思想，从出发点依次上下左右探索，没有走过的标记为1，走到走过的则后退
找到则方案数加一； 数据结构：利用二维数组进行迷宫的初始存放：边界条件：1.走出二维数组则continue；被标记的为1，回溯 恢复为 0。
dfs探索方向：上下左右
这个题目出现的回溯探测的情况，所以有标记现场，也有恢复现场
#include<bits/stdc++.h> using namespace std; const int N = 110; int n,m,t,sx,sy,fx,fy,res=0; int g[N][N]; // 坐标画 int a,b;//障碍物坐标 int dx[4]={-1,0,1,0};// int dy[4]={0,1,0,-1};//建立网格，进行dfs探索 void dfs(int x,int y){ if(x==fx&&y==fy){ res++; return; } for(int i = 0;i<4;i++){ int a = x+dx[i],b=y+dy[i];//dfs每次探寻的方向上下左右依次遍历 if(a<1||a>n||b<1||b>m) continue; if(g[a][b]) continue;//如果被访问过，则标记为1， g[a][b] = 1;//标记现场 dfs(a,b); g[a][b]=0;//回复现场 } } int main(){ cin>> n>>m>>t;//输入迷宫长度和宽度，以及障碍物数量 cin>>sx>>sy>>fx>>fy;//输入开始坐标和终点坐标 for(int i =0;i<t;i++){ cin>>a>>b;//输入障碍物坐标； g[a][b]=1;//设置障碍物坐标 } g[sx][sy] = 1;//设置开始位置； dfs(sx,sy); cout<<res; return 0; }3.P1644 跳马问题 - 洛谷
思路，主要是探照灯的探索，走马日，由题意只能向右边走，以（0，0）为原点，竖着x轴，水平y轴， 走马日有 （2，1）、 （1，2）（-2，1）、（-1，2）右半边
注意这里是以竖着x轴，水平y轴 ///
不需要进行存储迷宫障碍
#include<bits/stdc++.h> using namespace std; int n,m,res=0; int dx[4]={2,1,-1,-2};//走马日 （2，1）,(1,2),(-1,2),(-2,1)//右半边 int dy[4]={1,2,2,1}; void dfs(int x,int y){ if(x==n&&y==m){ res++; return; } for(int i =0;i<4;i++){ int a = x+dx[i],b = y+dy[i]; if(a<0||a>n||b>m||b<0)//竖着为x轴，水平为y轴 continue; dfs(a,b); } } int main(){ cin>>n>>m; dfs(0,0); cout<<res; return 0; }4.八皇后--3472. 八皇后 - AcWing题库- dfs 思路：递归回溯，标记
n 皇后
对角线元素的位置q[i+j] p[i-j+n]
左上到右下对角线判断： p[i-j+n]这对角线的值都一致（副对角线）
右上到左下对角线判断 ：q[i+j] 这对接线上的值都一致（主对角线）
#include<bits/stdc++.h> using namespace std; int n,ans; const int N = 20; //p对角线（i+j），q为对角线2(i-j+n) int pos[N],p[N],q[N],c[N];//pos数组标记第i行是否的第j列是否有皇后 void print(){//打印每一行的皇后，前三种方案 if(ans<=3){ for(int i= 1;i<=n;i++) cout<<pos[i]<<" ";//用一个一维数组存放每个皇后的位置，超过棋盘列数，则换行 cout<<endl; } } void dfs(int i){ if(i>n){//i>n表示棋盘都调用遍历完 ans++;//方案数 print(); return; } for(int j =1;j<=n;j++){ if(c[j]||p[i+j]||q[i-j+n]) continue;//判断是否被占用 pos[i]=j;//放置皇后 标记列号 c[j]=p[i+j]=q[i-j+n]=1;//标记占用 dfs(i+1);//递归下一行 c[j]=p[i+j]=q[i-j+n]=0; //回溯取消标记 } } int main(){ cin>>n; dfs(1); cout<<ans<<endl;//输出方案数 return 0; }