标签 深度优先搜索 下的文章
- 首页
- 深度优先搜索
[题解]洛谷P1189：`SEARCH`
切完这道题我只有一句话想说：DFS要打标……原题链接：P1189 `SEARCH`本题既可DFS又可BFS，输入输出也颇具可视化风格（但样例敲的真心累死），不过首次提交却只有30分，好端端一dfs你给我跑T……那么我也没话可说。暴搜路径这种操作没什么需要注意的。但是打标记就很重要了。经过思考我们可以发现搜索中存在很大重复的部分，在同一深度可能会对一个相同的点进行很多次搜索，极大地浪费了时间，...
[题解]洛谷P1605：迷宫
起因是最近教练讲了DFS，找水题做的时候发现这题我只有40分？！于是就随手把它清算了。原题链接：P1605 迷宫大概是珂以DP的，但是数据范围小的一批用DFS也能3ms搜过去。开一个N*M大小的布尔型标记数组维护能不能走，设计函数dfs(nx,ny)搜索从坐标(nx,ny)到(FX,FY)的路径；显然，对一个点至多有四种走法（上下左右），但需要事先判断合不合法（直接看标记），于是就宏定义一个...