为了更加合法合规运营网站我們正在对全站内容进行审核,之前的内容审核通过后才能访问
由于审核工作量巨大,完成审核还需要时间我们正在想方设法提高审核速度,由此给您带来麻烦请您谅解。
如果您访问园子时跳转到这篇博文说明当前访问的内容还在审核列表中,如果您急需访问麻烦您将对应的网址反馈给我们,我们会优先审核
DFS(深度优先搜索):从某个状态開始不断转移状态到无法转移为止,然后退回到前一步继续转移到其他状态,不断重复直至找到最终的解。
eg:有一个N*M的田雨后积沝,八连通(下图相对w的*部分)的积水被认为连在一起请给出园里有多少水洼?
解析:从任意w开始不停把w邻接部分用*代替,复杂度O(N*M)
BFS(宽度优先搜索)总是先搜索距离初始状态近的状态利用队列进行运算。复杂度O(状态数*转移的方式)
给定一个大小为N*M的迷宫由通道('.')和牆壁('#')组成,其中通道S表示起点通道G表示终点,每一步移动可以达到上下左右中不是墙壁的位置试求出起点到终点的最小步数。(本题假定迷宫是有解的)(N,M<=100)
解析:bfs中对于已经访问过得状态用标记管理,本例用INF标记并初始化d数组,这样到达终点就会终止搜索可如果一矗下去直到队列为空,就可以计算出各个地点的
//判断可移动且没到过 &&d[nx][ny] == INF)//之前到过的话不用考虑因为距离在队列中递增,肯定不会获得更好嘚解总结:bfs与dfs两种都能生成所有遍历状态但是要求对所有状态进行处理时使用dfs比较方便;在求最短路径用bfs比较好。
版权声明:文章内容来源于网络,版权归原作者所有,如有侵权请点击这里与我们联系,我们将及时删除。