NOIP学习小站搜索与回溯算法（1）——基础
搜索与回溯是计算机解题中常用的算法。搜索的策略是先选择一个起点开始向前探索，逐渐扩大寻找范围，在探索过程中一旦发现之前的选择是错误的，就退回一步重新选择（回溯），继续向前探索，如此反复进行，直到得到解或者证明问题无解。回溯是搜索算法的一种控...
搜索
搜索与回溯算法（2）——例题
一、数的拆分 问题：任何一个大于 1 的自然数 ，总可以拆分成若干个小于 的自然数的和。例如当 时，一共有 14 种拆分方法： 输入自然数 ，按照上面的格式输出拆分方案和方案种数。 分析：使用深度优先搜索算法，对于自然数 ，拆分出来一个整数...
搜索与回溯算法（3）——剪枝
DFS算法通过在函数内使用循环枚举下一步（或者是当前步）的所有情况，并在循环体中递归调用函数，实现了在当前基础上进一步搜索。如果根据题意可以严格限制循环枚举的条件（减少循环枚举的次数）或者在循环体中额外添加更全面的进一步递归搜索的条件，这两...
广度优先搜索（1）——基础
接下来介绍另一种搜索算法——广度优先搜索（BFS，有时候又称之为宽度优先搜索）。广度优先搜索比深度优先搜索简单，也更容易理解。如果一个问题两种搜索策略都能解决，一般情况推荐使用广度优先搜索，因为广度优先搜索的时间复杂度一般会低于深度优先搜索...
广度优先搜索（2）——例题
一、走迷宫 问题：迷宫是一个正方形，边长为 ，迷宫中的小格子（一共 个）有些能走通（标记 1），有些是墙壁（标记 0）。输入迷宫边长 和迷宫内部情况（ 行 列1、0整数），计算从迷宫左上角出发，到达右下角，最少需要走多少步？ 分析：这里要求...