机试搜索----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;ine[i]){//~i 相当于 i -1 int j e[i]; if(jfa) continue;//如果与父节点一样则跳过 // 题意计算过程 // dfs(j,u);//再次递归 } }题目1.求树高度///注意如果有超时错误则把cin和cout改为scanf和printf这两个两者效率高#includebits/stdc.h using namespace std; const int N 10010,M2*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;ine[i]){//下条边为 i ne[i] int j e[i]; if(jfa) 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 i0;in-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进行存放字符串以及距离#includebits/stdc.h using namespace std; int main(){ int n; scanf(%d,n); if(n4){ cout-1endl; return 0; } char strArr[20] {0};//初始化 scanf(%s,strArr); string str strArr; queuestring tovisit;//队列 tovisit.push(str);//入队 unordered_mapstring,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;icur.size()-1;i){//对字符串的每个字母进行对换 string next cur; swap(next[i],next[i1]); 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探索方向上下左右这个题目出现的回溯探测的情况所以有标记现场也有恢复现场#includebits/stdc.h using namespace std; const int N 110; int n,m,t,sx,sy,fx,fy,res0; 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(xfxyfy){ res; return; } for(int i 0;i4;i){ int a xdx[i],bydy[i];//dfs每次探寻的方向上下左右依次遍历 if(a1||an||b1||bm) continue; if(g[a][b]) continue;//如果被访问过则标记为1 g[a][b] 1;//标记现场 dfs(a,b); g[a][b]0;//回复现场 } } int main(){ cin nmt;//输入迷宫长度和宽度以及障碍物数量 cinsxsyfxfy;//输入开始坐标和终点坐标 for(int i 0;it;i){ cinab;//输入障碍物坐标 g[a][b]1;//设置障碍物坐标 } g[sx][sy] 1;//设置开始位置 dfs(sx,sy); coutres; return 0; }3.P1644 跳马问题 - 洛谷思路主要是探照灯的探索走马日由题意只能向右边走以00为原点竖着x轴水平y轴 走马日有 21、 12-21、-12右半边注意这里是以竖着x轴水平y轴 ///不需要进行存储迷宫障碍#includebits/stdc.h using namespace std; int n,m,res0; int dx[4]{2,1,-1,-2};//走马日 21,(1,2),(-1,2),(-2,1)//右半边 int dy[4]{1,2,2,1}; void dfs(int x,int y){ if(xnym){ res; return; } for(int i 0;i4;i){ int a xdx[i],b ydy[i]; if(a0||an||bm||b0)//竖着为x轴水平为y轴 continue; dfs(a,b); } } int main(){ cinnm; dfs(0,0); coutres; return 0; }4.八皇后--3472. 八皇后 - AcWing题库- dfs 思路递归回溯标记n 皇后对角线元素的位置q[ij] p[i-jn]左上到右下对角线判断 p[i-jn]这对角线的值都一致副对角线右上到左下对角线判断 q[ij] 这对接线上的值都一致主对角线#includebits/stdc.h using namespace std; int n,ans; const int N 20; //p对角线ijq为对角线2(i-jn) int pos[N],p[N],q[N],c[N];//pos数组标记第i行是否的第j列是否有皇后 void print(){//打印每一行的皇后前三种方案 if(ans3){ for(int i 1;in;i) coutpos[i] ;//用一个一维数组存放每个皇后的位置超过棋盘列数则换行 coutendl; } } void dfs(int i){ if(in){//in表示棋盘都调用遍历完 ans;//方案数 print(); return; } for(int j 1;jn;j){ if(c[j]||p[ij]||q[i-jn]) continue;//判断是否被占用 pos[i]j;//放置皇后 标记列号 c[j]p[ij]q[i-jn]1;//标记占用 dfs(i1);//递归下一行 c[j]p[ij]q[i-jn]0; //回溯取消标记 } } int main(){ cinn; dfs(1); coutansendl;//输出方案数 return 0; }