Java蓝桥杯学习第三章搜索

DFS基础DFS概念DFS(深度优先搜索)是基于递归求解问题而针对搜索的过程。我们约定对于问题的介入状态叫初始状态,要求的状态叫目标状态。这里的搜索就是对实时产生的状态进行分析检测直到得到一个目标状态或符合要求的最佳状态为止。对于实时产生新的状态的过程叫扩展搜索的要点:1. 选定初始状态在某些问题中可能是从多个合法状态分别入手搜索2. 遍历自初始状态或当前状态所产生的合法状态产生新的状态并进入递归3. 检查新状态是否为目标状态是则返回否则继续遍历,重复2-3步骤DFS模板public static void dfs(){ if(当前状态目标状态){ //逻辑处理 return; } for(寻找新状态){ if(状态合法){ dfs(新状态); } } }例题实战题目描述有一间长方形的房子地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上只能向相邻上下左右四个方向)的黑色瓷砖移动。请写一个程序计算你总共能够到达多少块黑色的瓷砖。输入第一行两个正整数nm。接下来输入一个二维字符矩阵每个字符为“.”“#”“”分别代表黑色瓷砖红色瓷砖黑色瓷砖初始位置。输出输出一个整数表示可以到达的瓷砖数。样例输入9 6. . . . # .. . . . . #. . . . . .. . . . . .. . . . . .. . . . . .. . . . . .# . . . #. # . . # .样例输出45就是初始状态黑色瓷砖就是合法状态public class BlackTileReachCount { //访问到的黑色瓷砖数 static int ans0; public static void main(String[] args) { Scanner scan new Scanner(System.in); int n scan.nextInt(); int m scan.nextInt(); char[][] c new char[n][m]; for(int i0;in;i){ c[i]scan.next().toCharArray(); } for(int i0;in;i){ for(int j0;jm;j){ if(c[i][j]) dfs(i,j,c); } } System.out.println(ans); } public static void dfs(int x,int y,char[][] c){ //进入搜索,黑色瓷砖1 ans; //这块黑色瓷砖参与计数,不能再用 c[x][y]#; //上下左右四个格子可走 int[] dx{1,-1,0,0}; int[] dy{0,0,1,-1}; for(int i0;i4;i){ int x1xdx[i]; int y1ydy[i]; //判断状态是否合法 //瓷砖不合法,跳出 if(x10||x1c.length||y10||y1c[0].length||c[x1][y1]!.)continue; //瓷砖合法 dfs(x1,y1,c); } } }DFS回溯回溯概念回溯算法的基本思想是从一条路往前走能进则进不能进则退回来换一条路再试从而搜索到抵达特定终点的一条或者多条特定路径。回溯在于“状态”在回溯算法向前的每一步你都会去设置某个状态而当向前走走不通的时候回退此时需要把之前设置的状态撤销掉。回溯模板public static void dfs(){ if(当前状态目标状态){ //逻辑处理 return; } for(寻找新状态){ if(状态合法){ //标记当前状态已访问 dfs(新状态); //撤销标记 } } }例题实战例一输入一个数组n输出1到n的全排列public class FullPermutationOf1ToN { //定义一个静态全局列表 list用于存储 1~n 的所有全排列结果 static ListListIntegerlistnew ArrayListListInteger(); public static void main(String[] args) { Scanner scannew Scanner(System.in); int nscan.nextInt(); //创建访问标记数组长度为n1 //因为数字是 1~n数组索引从 0 开始用索引 1~n 对应数字 1~n 更直观 // v[i]1 表示数字i已被选入当前排列v[i]0 表示未被选中 int[] vnew int[n1]; //创建临时列表用于存储当前正在构造的排列 //例如构造[1,2,3]的过程中res 会依次添加 1、2、3 ListInteger resnew ArrayList(); dfs(n,v,res); for (ListInteger x : list) { for (int y : x) { System.out.print(y ); } System.out.println(); } } public static void dfs(int n,int[] v,ListInteger res){ //当临时列表res的长度等于 n 时说明已经构造出一个完整的排列 if(res.size()n){ //将当前排列存入全局列表list //注意必须用new ArrayList(res)而不是直接list.add(res) //res是引用类型直接添加会导致后续回溯修改res时list中的元素也被修改 //新建列表可以保存当前状态的排列 list.add(new ArrayList(res)); return; } //查找新状态 for(int i1;in;i){ //表示当前数被访问过了,跳过查找 if(v[i]1)continue; res.add(i); //标记 v[i]1; //递归调用新状态 dfs(n,v,res); //加入的删除 res.remove(res.size()-1); //标记成未访问 v[i]0; } } }例二开心public class KLevelHappinessDifference { // 全局变量存储所有合法插法的最大和、最小和 // 初始化max设为Long最小值确保任何合法和都能覆盖它min设为Long最大值同理 static long max Long.MIN_VALUE, min Long.MAX_VALUE; public static void main(String[] args) { Scanner scan new Scanner(System.in); // 将数字字符串拆分为字符数组便于逐个处理每个数字字符 char[] c scan.next().toCharArray(); // 需要插入的数量 int k scan.nextInt(); StringBuilder sb new StringBuilder(); dfs(0, c, k, sb); System.out.println(max - min); scan.close(); } /** * 深度优先搜索DFS核心方法穷举所有合法的插入方式 * param u 当前处理的字符下标从0开始到c.length-1结束 * param c 数字字符串拆分后的字符数组 * param k 剩余可插入的数量 * param sb 临时拼接字符串记录当前DFS路径的拼接结果 */ public static void dfs(int u, char[] c, int k, StringBuilder sb) { // 递归终止条件所有字符处理完毕u等于字符数组长度 if (u c.length) { // 合法插法判定恰好插完k个剩余可插数量为0 if (k 0) { // 拆分当前拼接字符串如123拆分为[12,3] String[] s sb.toString().split(\\); long res 0; // 计算当前插法的数字和 for (String x : s) { // 转为Long避免数字溢出数字串可能很长 res Long.valueOf(x); } // 更新全局最大和、最小和 max Math.max(max, res); min Math.min(min, res); } return; } // 不插入直接拼接当前字符 sb.append(c[u]); // 递归处理下一个字符u1剩余可插数不变k dfs(u 1, c, k, sb); // 回溯删除刚拼接的字符 sb.deleteCharAt(sb.length() - 1); // 插入 // 合法条件还有可插的k0或 不是最后一个字符不能在末尾插 if (k 0 u c.length - 1) { // 先拼当前字符再拼 sb.append(c[u]); sb.append(); // 递归处理下一个字符u1剩余可插数减1k-1 dfs(u 1, c, k - 1, sb); // 回溯先删再删当前字符 sb.deleteCharAt(sb.length() - 1); // 删除 sb.deleteCharAt(sb.length() - 1); // 删除当前字符 } } }DFS剪枝在搜索算法中优化就称为剪枝就是通过某种判断避免一些不必要的遍历过程形象的说就是剪去了搜索树中的某些“枝条”故称剪枝。应用剪枝优化的核心问题是设计剪枝判断方法即确定哪些枝条应当舍弃哪些枝条应当保留的方法。概况:在进行搜索算法的过程中将已知无意义的情况排除的行为叫做剪枝记忆化搜索记忆化搜索是在搜索过程中,会有很多重复计算,如果我们能记录一些状态的答案,就可以减少重复搜索量记忆化搜索的核心实现1. 首先,要通过一个数组记录已经存储下的搜索结果2. 状态表示,由于是要用数组实现,所以状态最好可以用数字表示3. 在每一状态搜索的开始高效的使用数组查看这个状态是否出现过如果已经做过直接调用答案如果没有则按正常方法搜索