一、写在前面兄弟们Day 21了离国赛越来越近了今天把DFS的几个经典题型翻出来重新做了一遍发现有些细节之前理解得不够透彻。这三道题都是蓝桥杯考场上高频出现的DFS模板题建议大家一定要手写一遍不要只看代码。今天的三道题N皇后问题 —— 经典回溯小朋友崇拜圈 —— 环检测DFS全球变暖 —— 连通块边界判断二、第一题N皇后问题难度⭐⭐⭐2.1 题目大意给一个 N×N 的棋盘放 N 个皇后要求任意两个皇后不能在同一行、同一列、同一对角线上。问有多少种合法的放法。N ≤ 10数据范围很小直接DFS枚举就行。2.2 解题思路这道题是回溯算法的教科书级例题。核心思想是按行枚举每一行放一个皇后然后检查这一行的每一列是否合法。关键是三个标记数组vis1[y]第 y 列是否被占用vis2[xy]主对角线左上到右下是否被占用vis3[x-yn]副对角线右上到左下是否被占用这里x-yn是为了防止数组下标越界因为 x-y 可能是负数。2.3 代码实现importosimportsysdefdfs(x):# 第x层皇后x从1开始ifxn1:globalans ans1return# 第x层的皇后枚举每一列foryinrange(1,n1):# 如果列、主对角线、副对角线都被占了跳过ifvis1[y]orvis2[xy]orvis3[x-yn]:continue# (x,y)是合法点打标记vis1[y]vis2[xy]vis3[x-yn]Truedfs(x1)# 回溯清空标记vis1[y]vis2[xy]vis3[x-yn]Falsenint(input())# 列、主对角线、副对角线是否标记vis1[False]*(n1)vis2[False]*(2*n1)vis3[False]*(2*n1)ans0dfs(1)print(ans)2.4 踩坑记录数组大小vis2和vis3要开2*n1因为xy最大是2nx-yn最大也是2n。回溯时机dfs(x1)之后一定要恢复标记否则会影响其他分支的搜索。N的范围N≤10DFS完全能跑不用想剪枝优化。三、第二题小朋友崇拜圈难度⭐⭐⭐3.1 题目大意班里有 N 个小朋友每个小朋友都有一个最崇拜的小朋友可以是自己。现在让他们坐成一个圈要求每个小朋友崇拜的人都在他的右手边。求满足条件的圈最多能坐多少人。3.2 解题思路这道题本质上是找有向图中的最大环。每个小朋友只有一个出边崇拜的人所以图的结构是基环树森林——每个连通块由一个环和若干指向环的树组成。我们只需要找到所有环然后取最大环的长度即可。DFS过程中记录每个节点是第几步访问到的vis[x]length如果下一个节点已经被访问过说明找到了环环的长度就是length - vis[a[x]] 1。3.3 代码实现importsys# 扩栈递归层数过大需要设置最大栈空间sys.setrecursionlimit(100000)nint(input())a[0]list(map(int,input().split()))# 标记数组vis[x]表示走到x用了多少步vis[0]*(n1)defdfs(x,length):# 记录走到x走了length步vis[x]length# 接下来走下一个点x崇拜的人是a[x]# 判断下一个点是否走过ifvis[a[x]]!0:# 如果走过说明成环了更新答案globalans ansmax(ans,length-vis[a[x]]1)else:# 没走过继续DFSdfs(a[x],length1)ans0foriinrange(1,n1):# 对于每个单独的连通块都要做一遍dfsifvis[i]0:dfs(i,1)print(ans)3.4 踩坑记录扩栈N 最大到 10^5递归深度可能很大必须sys.setrecursionlimit(100000)否则递归栈溢出。环的长度计算length - vis[a[x]] 1这里vis[a[x]]是环的起点被访问时的步数length是当前步数两者之差加1就是环的长度。每个连通块都要DFS因为图可能不连通有多个独立的基环树。四、第三题全球变暖难度⭐⭐⭐⭐4.1 题目大意给一张 N×N 的地图.是海洋#是陆地。上下左右相邻的陆地组成一座岛屿。由于全球变暖海平面上升岛屿边缘与海洋相邻的陆地会被淹没。问最后有多少座岛屿会完全消失所有陆地都被淹没。4.2 解题思路这道题是连通块DFS的变形。需要判断每个岛屿是否会完全消失。关键观察一座岛屿不会完全消失当且仅当它存在至少一个高地——即上下左右四个方向都是陆地的点。这种点不会被淹没。算法步骤遍历每个未访问的陆地DFS找到整个岛屿DFS过程中判断是否存在高地如果没有高地这座岛屿会被完全淹没答案14.3 代码实现importsys sys.setrecursionlimit(100000)defdfs(x,y):# 当前处于(x,y)打标记vis[x][y]1# 判断当前点是否为高地上下左右都是陆地if(0x-1nandmp[x-1][y]#and0x1nandmp[x1][y]#and0y-1nandmp[x][y-1]#and0y1nandmp[x][y1]#):globalflag flagTrue# 往四周岛屿扩展fordx,dyin[(1,0),(-1,0),(0,1),(0,-1)]:xx,yyxdx,ydyif0xxnand0yynandmp[xx][yy]#andvis[xx][yy]0:dfs(xx,yy)nint(input())mp[]vis[]for_inrange(n):mp.append(list(input().strip()))vis.append([0]*n)# 淹没岛屿的数量ans0foriinrange(n):forjinrange(n):ifmp[i][j]#andvis[i][j]0:# 表示当前岛屿是否存在高地flagFalsedfs(i,j)ifflagFalse:ans1print(ans)4.4 踩坑记录边界判断判断高地时一定要检查四个方向都在地图范围内否则数组越界。flag的位置flag必须在每个岛屿的DFS前重置为False否则上一个岛屿的结果会影响下一个。输入处理input().strip()去掉换行符避免把\n当成地图内容。扩栈N 可能比较大递归深度可能达到 N²保险起见还是扩一下栈。五、今日总结题目核心算法关键技巧易错点N皇后回溯DFS三个标记数组数组大小、回溯恢复小朋友崇拜圈环检测DFS记录步数找环扩栈、多连通块全球变暖连通块DFS判断高地边界判断、flag重置DFS是蓝桥杯必考算法这三道题覆盖了回溯、环检测、连通块三种经典场景。建议大家在理解代码的基础上关掉屏幕自己默写一遍这样才能真正掌握。明天继续肝动态规划专题兄弟们一起加油六、附录相关题目推荐蓝桥杯 1224. 迷宫蓝桥杯 1511. 剪邮票蓝桥杯 604. 方格分割如果觉得有帮助欢迎点赞收藏有问题评论区见