东莞网站建设哪个平台好wordpress 评论go跳转

当前位置： 首页 > news >正文

东莞网站建设哪个平台好,wordpress 评论go跳转,wordpress如何上传pdf,做设计的搜素材上什么网站好算法介绍#xff1a; 深度优先搜索#xff08;Depth-First Search#xff0c;简称DFS#xff09;是一种用于遍历或搜索树或图的算法。这种算法会尽可能深地搜索图的分支#xff0c;直到找到目标节点或达到叶节点#xff08;没有子节点的节点#xff09;#xff0c;然后…算法介绍 深度优先搜索Depth-First Search简称DFS是一种用于遍历或搜索树或图的算法。这种算法会尽可能深地搜索图的分支直到找到目标节点或达到叶节点没有子节点的节点然后回溯到上一个分支继续搜索。DFS可以用于许多问题比如路径寻找、连通性验证、拓扑排序等。 在ACM、蓝桥杯等著名竞赛中DFS算法是比较重要的特别是在蓝桥杯中每一年几乎都要考DFS/BFS算法。DFS算法在OI赛中用处非常大可以通过DFS/BFS暴力的方式可以拿到部分分数蓝桥杯一般可以拿到20%的分数有的甚至高达50%是暴力得分的不二之选。 基本步骤 DFS通常使用递归或栈来实现。以下是DFS的基本步骤 选择起始点选择图中的一个点作为起始点。访问节点标记起始节点为已访问并将该节点加入递归或栈中。探索邻接节点从该点周围取出一个点检查它的所有未访问的邻接节点。递归或迭代对每个未访问的邻接节点将其标记为已访问然后将其推入递归或栈中。回溯当当前节点的所有邻接节点都被访问后递归中回溯/从栈中弹出该节点继续搜索上一个点的其他分支。结束条件当栈为空或找到目标节点时搜索结束。 图解算法 下面放一张我们学校ACM在大一培训时使用的一张动态BFS/DFS步骤图。注红色遍历为BFS、黄色遍历为DFS。绿色为起点紫色为终点黑色为障碍物 由上图中我们可以看出DFS的遍历为一条路用我们学长的话说就是一条路走到头找不到就再回头换另一条路继续搜索直到找到终点。那么BFS就是在一个点的周围每一个点都走一遍试一下属于扩散型的。找不到的话在这个点的基础上再去扩散四周寻找。BFS一般通过栈来实现DFS一般通过递归来实现。 下面我们将以3*3的网格只考虑上下左右四个方向上左、下左等四个方向不考虑递归顺序为{上、下、左、右}顺序可按照自己的想法这里以上下左右顺序为例给大家模拟实现一下过程。 第一步 本身就在起点先把此时起点标记为已经走过了即vis[起点]true告诉后面这个点不能再搜索了不标记的话可能会陷入死循环。在寻找起点的上下左右格子我们发现{上}、{左}方向都已经超出了格子范围在题中就是超出了下标范围那么我们能考虑的就只有{下}、{右}方向由于我们递归的顺序为{上、下、左、右}{上}方向超出了格子范围那么级别最高且合法的就是{下}方向了从起点向下走。 第二步  先标记vis[第一步]true。此时我们发现{左}方向已经不在网格里面了下标已经越界了所以不考虑{左}方向此时递归顺序为{上、下、右}方向向上走在第一步一开始我们就把vis[起点]标记为true说明已经走过了下面不允许走了{上}方向也不能走了。此时优先级最高的为下方向了下方向没有被标记过所以可以走。 第三步  还是先标记把当前位置所走的标记为已经走过即vis[第二步]true。此时我们发现{左、下}两个方向已经越界了所以不考虑此时递归优先级为{上、右}由于第三步刚开始就把vis[第二步]true已经标记了不能走了所以这一步只能向右走。 第四步 还还还是先标记vis[第三步]true。此时我们发现{下}方向已经越界了所以不考虑{下}方向了在这一步刚开始我们把{左}方向这个点已经给标记过了所以不能走那么剩余的合法递归顺序为{上、右}此时我们便可以向上走找到终点完成此次DFS(深度优先搜索)。 算法模板 从上面的图解算法中步骤我们把算法步骤归结为一下 首先我们需要一个数组即输入的数据数组可能为int、也肯为char在绝大部分题目中都需要一个标记数组即bool类型的vis数组。然后在题目中找到搜索的起点跟终点设置dfs函数的参数根据题目的不同参数个数不同。在主函数dfs函数之前先把vis[起点]标记为true一定不要忘记否则就是死循环。确定了起点把参数传给dfs函数参数进入dfs递归函数确定函数的终止条件即当前状态目标状态或者递归值某个数等终止条件一定在函数的最前面否则会影响答案。再次在当前点寻找当前点的周围根据题目可能四个点也可能八个点等用for循环遍历每一个点如果这个点已经被标记过了或者数组下标越界都是不合法的直接continue掉。那么剩下的就是合法的可以访问下一个点先把下一个点给标记完再去递归下一个点再进入dfs函数递归注意大部分dfs都需要回溯的,即把vis[当前点]false,为什么需要回溯这就是我们所说的一条路走不通回头换一条路走那么我要回头前面走过的已经被标记的还咋走那就要vis[当前点]false解除标记。下面贴一个dfs函数的一般模板。 void dfs(int dep){//dep为当前状态if(depx){//当前状态目标状态终止条件更新结果return;}for(int i0;in;i){//遍历每一种可能if(不符合条件){continue;//跳过}//符合条件vis[访问的点]true;//先标记dfs(下一个状态);vis[访问的点]false;//恢复现场,大部分需要回溯,有的不需要这一步} } 算法例题 现在各大算法刷题网站上dfs题目非常的多dfs题目的变化也比较多现在各种各样的题目层出不穷博主所做过的题印象中大部分在终止条件哪里变化的比较多像是还有在条件判断上增加附加条件等等下面博主选取几个比较具有代表性的给大家讲解一下加深理解一下dfs算法。 一、马走日 题目描述 马在中国象棋以日字形规则移动。请编写一段程序给定n×m大小的棋盘以及马的初始位置(xy)要求不能重复经过棋盘上的同一个点计算马可以有多少途径遍历棋盘上的所有点。输入 第一行为整数T(T 10)表示测试数据组数。 每一组测试数据包含一行为四个整数分别为棋盘的大小以及初始位置坐标n,m,x,y。(0≤x≤n-1,0≤y≤m-1, m 10, n 10)。输出 每组测试数据包含一行为一个整数表示马能遍历棋盘的途径总数0为无法遍历一次。输入示例 1 5 4 0 0输出示例 32 解题思路 这个题不同在了马走的方向跟之前走四个方向的不同他是斜着跳与象棋上的马一样例如12、-21等初始状态就是起点x,y终点的话除了起点每个点都可能是终点这样不好确定终点但是我们有一个条件遍历完所有点有两种方法可以确定遍历完所有点第一种是n*m的棋盘那么如果走完了n*m步就完成了一次第二种设置一个标记数组标记棋盘上每一个点都被标记完了就完成一次很明显第一种方法比第二种好。由于统计的是途径总数每完成一次计数就,直到他无路可走自动退出函数。 AC代码 #includeiostream using namespace std; int a[15][15],vis[15][15]; int n,m,sx,sy; int ans;//途径数 int dx[]{1,1,-1,-1,2,2,-2,-2};//马在棋盘上可以跳八个方向 int dy[]{2,-2,2,-2,1,-1,1,-1}; void dfs(int x,int y,int dep){//x,y当前坐标dep当前步数if(depn*m){//终止条件ans;return;}for(int i0;i8;i){//八个方向遍历int bxxdx[i];int byydy[i];if(vis[bx][by]1){//已经被标记过了continue;}if(bx0||bxn||by0||bym){//下标越界continue;}vis[bx][by]1;//先标记该点dfs(bx,by,dep1);//再去递归下一次vis[bx][by]0;//回溯–解标记} } int main(){int t;cint;while(t–){ans0;scanf(%d%d%d%d,n,m,sx,sy);vis[sx][sy]1;//起点标记dfs(sx,sy,1);printf(%d,ans);}return 0; } 二、AcWing 3428. 放苹果 把 M个同样的苹果放在 N个同样的盘子里允许有的盘子空着不放问共有多少种不同的分法 盘子相对顺序不同例如 511和 151算作同一种分法。 输入格式 输入包含多组测试数据。 每组数据占一行包含两个整数 M 和 N。 输出格式 每组数据输出一行一个结果表示分法数量。 数据范围 1≤M,N≤10; 输入样例 7 3输出样例 8 解题思路 N与M最大只有10dfs可以适用M个苹果放到N个盘子里允许盘子空着不放可以直接dfs递归实现我们设置两个参数一个遍历的盘子数dep,一个遍历的苹果数sum,每一次向盘子里面放t个苹果那么苹果数sum-t盘子数sum1当超出了盘子数不符合条件或者苹果数0则返回上一步执行。 AC代码  #includeiostream using namespace std;int a[101]{1};//初始化为1放苹果的至少放一个 int m,n,num0;//m:苹果n:盘子void dfs(int sum,int dep){if(sum0){//没有苹果就没法放了回溯return;}if(sum0depn1){//终止条件num;return;}for(int ia[dep-1];im;i){//防止重复放比如{151}跟{511}是一样的放法a[dep]i;//放的个数dfs(sum-i,dep1);//继续搜索下一个盘子//没有回溯因为这是组合问题分的苹果数重复了属于同一种} } int main(){while(scanf(%d%d,m,n)!EOF){num0;dfs(m,1);printf(%d\n,num);}return 0; } 三、八皇后问题  会下国际象棋的人都很清楚皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。 如何将 8 个皇后放在棋盘上有 8×8 个方格使它们谁也不能被吃掉 这就是著名的八皇后问题。 已经知道 8 皇后问题一共有 92 组解。 要求打印每一种解。 解题思路 对于八皇后问题以后博主感觉不会出类似的题但是我还是想把八皇后加入到例题来讲解因为它实在是太经典了。八皇后问题是最经典的递归问题你可以说没学过八皇后但是不能说学了dfs但是不会八皇后。为什么说八皇后问题最经典八皇后问题的条件一般是不会改变的它在标记这一块动了手脚本来由标记一个点变为标记整行、整列、点所在的主对角线、点所在的副对角线。主要麻烦在了标记这一块标记处理好了回溯的时候也比较好处理现在对于标记网上有很多方法我看了很多方法找出了一种我认为比较好的方法是acking老师讲解的方法跟大家分享一下。 首先它需要标记四条线分别是行、列、上左到右下、上右到左下把它简化一下我每次遍历从第一行开始每次向下一个这样保证了每次行不一样可以少标记一个数组。列的话一个一维vis数组就够了上左到右下这条线把它顺时针旋转45°会发现是竖直的线。每一条线满足i-jn不一样ij是坐标。上右到左下这条线逆时针旋转45°也会发现是一条竖线每一条线满足ij是不一样的。这样可以把它们的值当作下标值处理。 视频讲解acking老师讲解—点击这里— 代码实现 #includestdio.h int a[10][10]; int vis1[8]/标记列/, vis2[16],/标记左上右下/ vis3[16]/标记右上左下/; int n 8, ans 0; void vis(int i, int j, int flag) {a[i][j] flag;vis1[j] flag;vis2[i - j n] flag;vis3[i j] flag; } void dfs(int i) {if (i n) {printf(No.%d\n, ans);for (int i 0; i n; i) {for (int j 0; j n; j) {printf(%d , a[i][j]);}printf(\n);}return;}for (int j 0; j n; j) {if (vis1[j] 0 vis2[i - j n] 0 vis3[i j] 0) {vis(i, j, 1);dfs(i 1);vis(i, j, 0);}} } int main() {dfs(0);return 0; } 四、第十四届蓝桥杯省赛大学B组 岛屿个数 题目描述 小蓝得到了一副大小为 M×N 的格子地图可以将其视作一个只包含字符 0代表海水和 1代表陆地的二维数组地图之外可以视作全部是海水每个岛屿由在上/下/左/右四个方向上相邻的 1 相连接而形成。 在岛屿 A 所占据的格子中如果可以从中选出 k 个不同的格子使得他们的坐标能够组成一个这样的排列(x0,y0),(x1,y1),…,(xk−1,yk−1)其中 (x(i1)%k,y(i1)%k) 是由 (xi,yi) 通过上/下/左/右移动一次得来的 (0≤i≤k−1)此时这 k 个格子就构成了一个 “环”。 如果另一个岛屿 B 所占据的格子全部位于这个 “环” 内部此时我们将岛屿 B 视作是岛屿 A 的子岛屿。若 B 是 A 的子岛屿C 又是 B 的子岛屿那 C 也是 A 的子岛屿。 请问这个地图上共有多少个岛屿在进行统计时不需要统计子岛屿的数目。 输入格式: 第一行一个整数 T表示有 T 组测试数据。 接下来输入 T 组数据。 对于每组数据第一行包含两个用空格分隔的整数 M、N 表示地图大小接下来输入 M行每行包含 N 个字符字符只可能是 0 或 1。 输出格式: 对于每组数据输出一行包含一个整数表示答案。 数据范围: 对于 30% 的评测用例1≤M,N≤10。 对于 100% 的评测用例1≤T≤101≤M,N≤50。 解题思路  这个题博主感觉是蓝桥杯出的比较成功的题它考查的非常具有思维性打破了传统的dfs思路。加入了新的判断条件很具有挑战性博主感觉以后的像蓝桥杯这种比赛dfs的考察一定会向着这个方向发展传统的dfs将会退出题海战术。具体的讲解跟AC代码请看我这一篇文章文章单独讲解了这一道题由于文章长度限制这里不再详解请移步下面链接。 第十四届省赛大学B组C/C岛屿个数-CSDN博客文章浏览阅读1.1k次点赞30次收藏14次。这不是普通的DFS/BFS搜索题看着很像最少连通块但是题目中又有了新的定义就是在陆地环里面被陆地包围也算属于此外围岛屿那么我们就也要判定这种环岛屿博主的思路是先BFS也可DFS找出连通块的个数四个方向建一个vector把连通块的起点存进去方便去找环岛屿只要有一个起点或者此连通块任意一个点此连通块的点便可通过移动一网打尽再BFS或者DFS判定该岛屿是否属于这种环岛屿不属于就结果加一属于就不用加。对于 100% 的评测用例1≤T≤101≤M,N≤50。https://blog.csdn.net/m0_73633807/article/details/137248445?spm1001.2014.3001.5501 感谢大家支持下篇更新BFS(广度优先搜索)