【进阶算法】DFS(7~10)

前言相信很多人学完基础算法(双指针。滑动窗口前缀和递归等等)学习搜索与图论于是我决定出一个教程大纲是这样的主要有回溯,DFS,BFS,图,最短路径这几块难理解望多支持点赞。Day1回溯总结 错题复盘Day2组合问题固定长度、剪枝、去重Day3排列问题used数组、顺序、去重Day4字符串切割类 DFS分割回文串Day5条件判断型 DFS复原IP地址Day6多集合回溯电话号码字母组合Day7棋盘 DFS 模型一维表示二维Day8N皇后基础棋盘回溯Day9解数独二维DFSDay10DFS 全题型模板大总结Day11BFS 思想 队列 层序遍历Day12网格 BFS岛屿、连通块Day13BFS 最短路径Day14图是什么 邻接表存图核心Day15图的 DFS 遍历Day16图的 BFS 遍历Day17Floyd–Warshall弗洛伊德全源最短路Day18Dijkstra迪杰斯特拉单源最短路Day19Bellman–Ford SPFA单源最短路处理负权Day20图论最短路算法总结 全套模板默写(DFS) Day7 棋盘 DFS 模型1. 单词搜索型 DFS 是什么单词搜索是二维网格上的路径回溯问题属于棋盘 DFS 的核心分支核心特征操作场景是 m×n 字符网格如字母矩阵核心目标从任意格子出发沿上下左右相邻格子不能重复走拼出目标单词核心逻辑选起点→尝试四个方向→匹配字符→标记已走→递归下一格→不匹配则回溯。简单理解像在字母迷宫里找单词从一个字母出发上下左右找下一个字母走过的格子不能回头直到拼出完整单词。2. 解决的核心问题适用于二维网格找路径 / 拼序列的场景单词搜索今天核心例题网格中找最长连续字符迷宫找通路字符版网格中找所有能拼出目标单词的起点。核心痛点既要匹配字符又要避免重复走格子还要处理多方向递归。3.例题(Leetcode 79)#includevector#includestringusingnamespacestd;classSolution{public:vectorvectorcharmaps;inta[4][2]{{-1,0},{0,1},{0,-1},{1,0}};vectorvectorboolused;string words;boolexist(vectorvectorcharboard,string word){if(board.empty()||board[0].empty()||word.empty())returnfalse;used.resize(board.size(),vectorbool(board[0].size(),false));mapsboard;wordsword;for(inti0;iboard.size();i){for(intj0;jboard[0].size();j){if(board[i][j]word[0]){// 找到初始used[i][j]true;if(dfs(1,i,j)){returntrue;}used[i][j]false;// 回溯}}}returnfalse;}booldfs(intdepth,intm,intn){if(depthwords.size())returntrue;for(intx0;x4;x){ints1ma[x][0];ints2na[x][1];if(s10s20s1maps.size()s2maps[0].size()!used[s1][s2]maps[s1][s2]words[depth]){// 判断合法used[s1][s2]true;if(dfs(depth1,s1,s2)){returntrue;}used[s1][s2]false;}}returnfalse;}};(DFS) Day8 N皇后问题1. 例题(Leetcode 52)#includevector#includestringusingnamespacestd;classSolution{public:intcount0;intn;inttotalNQueens(int_n){n_n;vectorstringboard(n,string(n,.));dfs(0,board);returncount;}voiddfs(introw,vectorstringboard){if(rown){count;return;}for(intcol0;coln;col){if(isValid(board,row,col)){board[row][col]Q;dfs(row1,board);board[row][col].;// 回溯}}}boolisValid(vectorstringboard,introw,intcol){for(inti0;irow;i){if(board[i][col]Q)returnfalse;}for(intirow-1,jcol-1;i0j0;i--,j--){if(board[i][j]Q)returnfalse;}for(intirow-1,jcol1;i0jn;i--,j){if(board[i][j]Q)returnfalse;}returntrue;}};(DFS) Day9 数独问题1. 例题(LeetCode 37)classSolution{public:voidsolveSudoku(vectorvectorcharboard){dfs(board);}booldfs(vectorvectorcharboard){// 遍历每个格子for(inti0;i9;i){for(intj0;j9;j){if(board[i][j]!.)continue;// 尝试填 1~9for(charc1;c9;c){if(ok(board,i,j,c)){board[i][j]c;if(dfs(board))returntrue;board[i][j].;}}returnfalse;}}returntrue;}// 判断在 (x,y) 填 c 是否合法boolok(vectorvectorcharboard,intx,inty,charc){for(inti0;i9;i){if(board[x][i]c)returnfalse;// 行if(board[i][y]c)returnfalse;// 列}// 3×3宫格intax/3*3;intby/3*3;for(inti0;i3;i){for(intj0;j3;j){if(board[ai][bj]c)returnfalse;}}returntrue;}};(DFS) Day10 DFS总复习1. 组合 / 子集工具startIndex不回头、不排序2. 排列工具used 数组全遍历、讲究顺序3. 字符串切割工具start、substr切割 合法性判断4. 多集合回溯工具depth按集合顺序选5. 棋盘 DFSN 皇后逐行 三方向检查数独空格 三约束检查网格四方向扩散题型核心变量遍历方式去重 / 剪枝回溯操作组合问题startIndexi start; i n排序 i start nums[i]nums[i-1]push_back / pop_back排列问题used 数组i 0; i n排序 !used[i-1] nums[i]nums[i-1]used[i] true/false字符串切割起点 starti start; i s.size()回文判断 / 长度限制push_back / pop_back复原 IP段数 depth最多 3 位0255、无前导 0字符串拼接 / 截断电话号码组合位数 depth对应数字的字母集无字符追加 /pop_back棋盘一维 DFSindex0 ~ n*n-1放 / 不放二选一标记 / 取消标记N 皇后行 row列 col 循环列、两斜线检查放Q/ 恢复.解数独坐标 (i,j)逐格找.行 / 列 / 3×3 宫不重复填数字 / 恢复.恭喜大家DFS学习完毕下一期想要练习的扣1学习BFS扣2点点赞谢谢了