*搜索算法(2)

持续更新··· 1.递归型枚举与回溯剪枝初识 1. 画决策树； 2. 根据决策树写递归 【题⽬描述】 今有 n 位同学，可以从中选出任意名同学参加合唱。 请输出所有可能的选择⽅案。 【输⼊描述】 仅⼀⾏，⼀个正整数 n 。 【输出描述】 若⼲⾏，每⾏表⽰⼀个选择⽅案。 每⼀种选择⽅案⽤⼀个字符串表⽰，其中第 位为 Y 则表⽰第 名同学参加合唱；为 N 则表⽰ 不参加。 i i 需要以字典序输出答案。 设计递归函数： *重复⼦问题：针对某⼀位，「选」或者「不选」这个数。因为最终结果要按照「字典序」输出，我们可以「先考虑不选」，然后「再考虑选」；

【题⽬描述】 从 1 ∼ n 这 n 个整数中随机选出 m 个，输出所有可能的选择⽅案。 【输⼊描述】 两个整数 n , m ，在同⼀⾏⽤空格隔开。 【输出描述】 按照从⼩到⼤的顺序输出所有⽅案，每⾏ 1 个。 ⾸先，同⼀⾏内的数升序排列，相邻两个数⽤⼀个空格隔开。 其次，对于两个不同的⾏，对应下标的数⼀⼀⽐较，字典序较⼩的排在前⾯（例如 1 3 5 7 排 在 1 3 6 8 前⾯）。

【题⽬描述】 今有 n 名学⽣，要从中选出 k ⼈排成⼀列拍照。 请按字典序输出所有可能的排列⽅式。 【输⼊描述】 仅⼀⾏，两个正整数 n , k 。 对于 100% 的数据， 1 ≤ k ≤ n ≤ 10 。 【输出描述】 若⼲⾏，每⾏ k 个正整数，表⽰⼀种可能的队伍顺序

 2.DFS

3.剪枝与优化 【题⽬描述】 将整数 n 分成 k 份，且每份不能为空，任意两个⽅案不相同（不考虑顺序）。 例如： n = 7, k = 3 ，下⾯三种分法被认为是相同的。 1, 1, 5 1, 5, 1 5, 1, 1 问有多少种不同的分法。 【输⼊描述】 n , k （ 6 < n ≤ 200 ， 2 ≤ k ≤ 6 ） 【输出描述】 1 个整数，即不同的分法。 注意剪枝位置的不同，而导致搜索树的不同： 1.如果在进⼊递归之前剪枝，我们不会进入非法的递归函数中； 2.但是如果在进⼊递归之后剪枝，我们就会多进⼊很多不合法的递归函数中。 【题⽬描述】 Freda 和 rainbow 饲养了 N ( N ≤ 18)  只⼩猫，这天，⼩猫们要去爬⼭。经历了千⾟万苦，⼩猫们 终于爬上了⼭顶，但是疲倦的它们再也不想徒步⾛下⼭了 Freda 和 rainbow 只好花钱让它们坐索道下⼭。索道上的缆⻋最⼤承重量为 W ，⽽ N 只⼩猫的重 量分别是 C1,C2,,,,,CN。当然，每辆缆⻋上的⼩猫的重量之和不能超过 W (1 ≤ C i ≤ W ≤ 10^8) 。每租⽤⼀辆缆⻋，Freda 和 rainbow 就要付 1 美元，所以他们想知道，最少需要付多少美元才能把这 N 只⼩猫都运送下⼭？ 【输⼊描述】 第⼀⾏包含两个⽤空格隔开的整数， N 和 W 。 接下来 N ⾏每⾏⼀个整数，其中第 i + 1 ⾏的整 数表⽰第 i 只⼩猫的重量 C i 。 【输出描述】 输出⼀个整数，最少需要多少美元，也就是最少需要多少辆缆⻋。 搜索策略：对于每每⼀只猫，我们都有两种处理⽅式： *要么把这只猫放在已经租好的缆⻋上； *要么重新租⼀个缆⻋，把这只猫放上去。

 4.记忆化搜索 记忆化搜索也是⼀种剪枝策略。 通过⼀个"备忘录"，记录第⼀次搜索到的结果，当下⼀次搜索到这个状态时，直接在"备忘录"⾥⾯找结果。 记忆化搜索，有时也叫动态规划。 【题⽬描述】 斐波那契数 （通常⽤ F(n) 表⽰）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后 ⾯的每⼀项数字都是前⾯两项数字的和。也就是： F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1 给定 n ，请计算 F(n) 。 【算法原理】 在搜索的过程中，如果发现特别多完全相同的⼦问题，就可以添加⼀个备忘录，将搜索的结果放在备忘录中。下⼀次在搜索到这个状态时，直接在备忘录⾥⾯拿值

5.BFS 宽度优先搜索的过程中，每次都会从当前点向外扩展⼀层，所以会具有⼀个最短路的特性。因此，宽搜不仅能搜到所有的状态，⽽且还能找出起始状态距离某个状态的最⼩步数。 但是，前提条件是每次扩展的代价都是1 ，或者都是相同的数。宽搜常常被⽤于解决边权为 1的最 短路问题。 【题⽬描述】 有⼀个 的棋盘，在某个点 上有⼀个⻢，要求你计算出⻢到达棋盘上任意⼀个点最少 要⾛⼏步。 n × m ( x , y ) 【输⼊描述】 输⼊只有⼀⾏四个整数，分别为 n , m , x , y 。 【输出描述】 ⼀个 n × m 的矩阵，代表⻢到达某个点最少要⾛⼏步（不能到达则输出 −1 ）。

 【题⽬描述】

FJ 丢失了他的⼀头⽜，他决定追回他的⽜。已知 FJ 和⽜在⼀条直线上，初始位置分别为x 和y ， 假定⽜在原地不动。FJ 的⾏⾛⽅式很特别：他每⼀次可以前进⼀步、后退⼀步或者直接⾛到2*x 的位置。计算他⾄少需要⼏步追上他的⽜。 【输⼊描述】 第⼀⾏为⼀个整数 t (1 ≤ t ≤ 10) ，表⽰数据组数； 接下来每⾏包含⼀个两个正整数 x , y (0 < x , y ≤ 10 ) 5 ，分别表⽰ FJ 和⽜的坐标。 【输出描述】 对于每组数据，输出最少步数。

 八数码难题

【题⽬描述】 在 的棋盘上，摆有⼋个棋⼦，每个棋⼦上标有 1⾄8 的某⼀数字。棋盘中留有⼀个空格，空格⽤ 0来表⽰。空格周围的棋⼦可以移到空格中。要求解的问题是：给出⼀种初始布局（初始状态）和⽬标布局（为了使题⽬简单,设⽬标状态为123804765 ），找到⼀种最少步骤的移动⽅法，实现从初始布局到⽬标布局的转变。 【输⼊描述】 输⼊初始状态，⼀⾏九个数字，空格⽤ 0 表⽰。 【输出描述】 只有⼀⾏，该⾏只有⼀个数字，表⽰从初始状态到⽬标状态需要的最少移动次数。保证测试数据中⽆ 特殊⽆法到达⽬标状态数据。 6.多源BFS 多源最短路问题的边权都为 1 时，此时就可以⽤多源 BFS 来解决。 把这些源点汇聚在⼀起，当成⼀个"超级源点"。然后从这个"超级源点"开始，处理最短路问题。落实到代码上时： 1. 初始化的时候，把所有的源点都加⼊到队列⾥⾯； 2. 然后正常执⾏ bfs 的逻辑即可。 也就是初始化的时候，⽐普通的 bfs 多加⼊⼏个起点。 题：刺杀大使 7.01BFS

8.floodfill问题