算法1-7 搜索

目录

1 深度优先搜索

1.1 P1219 八皇后 

 1.2 P1135 深搜+剪枝

1.3 P1605 多路深搜+回溯

 2 广度优先搜索

2.1 P1443 马的遍历

3 多方向搜索 

3.1 P1101 单词方阵

1 深度优先搜索

需要考虑深度的情况：

  • 固定长度组合：当问题要求生成确定长度的组合（如从n个元素中选择k个）时，必须通过深度参数（或计数器）跟踪已选元素的数量。例如，在生成组合C(n, k)时，若当前路径长度等于k，则终止递归。
  • 剪枝优化：深度参数可用于剪枝，提前终止无法满足长度条件的路径，提高效率。

不需考虑深度的情况：

  • 所有子集生成：当问题允许任意长度的组合（如求所有子集）时，无需显式跟踪深度。DFS会通过元素索引隐式控制递归层次，遍历所有可能的选与不选路径，最终生成所有子集。

不考虑深度的结果：

  • 若问题本需固定长度但未控制深度，DFS将生成所有可能的子集（包含不同长度），而非目标长度的组合。
  • 若问题允许任意长度，正确实现的DFS（通过索引控制遍历顺序）会列举所有组合情况。

1.1 P1219 八皇后 

思路：

  • 题目要求找到满足条件的解，我们需要去搜索可行解，每行进行一次递归，找到对应值
  • 难点：判断该点的两条对角线上没有其他点，即标记该点对角线的使用状态
  • 使用四个数组分别代表行，列，两条对角线，左上到右下的对角线y-i是个定值，为避免y-i<0,令y-i+n，偏移n个单位，依然对应每条对角线即可；左下到右上的对角线i+j为定值，所以只需要使用两个数组来保存每条对角线是否使用即可
package SouSuo;
import java.util.Scanner;public class P1219 {public static int count=0;public static int n;// 记录每行存储的列下标static int[]a;// 记录哪一列被使用static int[]b;// 左下到右上对角线static int[]c;// 左上到右下对角线static int[]d;public static void main(String[] args) {Scanner scanner=new Scanner(System.in);n = scanner.nextInt();a=new int[n+1];b=new int[n];c=new int[2*n];d=new int[2*n];dfs(1);System.out.println(count);}public static void dfs(int index){if (index>n){if (count<3){for (int i = 1; i <=n ; i++) {System.out.print(a[i]+" ");}System.out.println();}count++;return;}for (int i = 0; i < n; i++) {// 第i列未使用 该位置的左下到右上的对角线行+列固定值位index+iif (b[i]==0 && c[index+i]==0 && d[i-index+n]==0){b[i]=1;c[index+i]=1;d[i-index+n]=1;// index是行号 i是列a[index]=i+1;dfs(index+1);b[i]=0;c[index+i]=0;d[i-index+n]=0;}}}
}

 1.2 P1135 深搜+剪枝

思路：

  • 每层楼梯都可以上或者下，可以分两路递归，一路上，一路下
  • 方法开始时对当前层判断是否合法，而不在上楼和下楼前判断其合法性
  • 关键点：剪枝
    • 当前层数大于最大层或者小于最低层，索引位置不合法
    • 在不断上下楼的过程中，一层楼会反复到达，从这层楼到达其它楼层的方案又一致，导致大量的重复计算，使用一个数组记录到达每层时的最小步数，如果下次到达该层时>=该步数，直接返回
    • 有了上述两次剪枝后，可能达到某个点时花费了5步，比之前到达这个点花费的步数少，但可能之前3步就走到了最终点，即当前方案应该舍去，直接return，即第三种剪枝

1.3 P1605 多路深搜+回溯

思路：

  • 从起点到终点，搜索有多少条可行路径，每段路径一个点只能走一次
  • 采用深度搜索，多路递归模拟上下左右四种选择情况
  • 使用flags数组标记该点的状态，当从这个点出发，上下左右都走完时，会回到上一个出发点，重新开始一条路径，则将当前点回溯为false

细节：

  • 每次对当前点做越界判断，而不是判断该点是否可以向左走，向右走，向上走，向下走等多种情况
package SouSuo;import java.util.Scanner;public class P1605 {public static int n;public static int m;public static int sx;public static int sy;public static int fx;public static int fy;public static int count;public static void main(String[] args) {Scanner scanner=new Scanner(System.in);n = scanner.nextInt();m = scanner.nextInt();int t = scanner.nextInt();sx = scanner.nextInt();sy = scanner.nextInt();fx = scanner.nextInt();fy = scanner.nextInt();int[][] array=new int[n+1][m+1];for (int i = 0; i < t; i++) {// 障碍点array[scanner.nextInt()][scanner.nextInt()]=-1;}boolean[][]flags=new boolean[n+1][m+1];dfs(array,flags,sx,sy);System.out.println(count);}public static void dfs(int[][] array,boolean[][]flags,int x,int y){if (x<=0 || y<=0 || x>n ||y>m){return;}if (array[x][y]==-1){// 这个点是障碍点return;}if (x==fx && y==fy){count+=1;return;}if (flags[x][y]){return;}flags[x][y]=true;dfs(array,flags,x+1,y);dfs(array,flags,x-1,y);dfs(array,flags,x,y+1);dfs(array,flags,x,y-1);// 这个点上下左右都走完了 回溯到上一个点 把这个点放掉flags[x][y]=false;}
}

 2 广度优先搜索

2.1 P1443 马的遍历

思路：

  • 题目给了一个初始点，问马到棋盘上其它点的最小步数，采用广度优先搜索，因为要的是最小步数，马在选择下一个点时有多种情况，而这多种情况是在同一层的，即步数相等，而不应该逐渐增加
  • 下一个点的步数等于当前点的步数+1,不需要采用count计数，不然还需要考虑count回溯问题

细节：

  • 马可以有八种选择，使用两个数组dx,dy分别代表对应一组数据的变化情况，避免if枚举
package SouSuo;import java.util.LinkedList;
import java.util.Scanner;public class P1443 {public static int n;public static int m;public static void main(String[] args) {Scanner scanner=new Scanner(System.in);n = scanner.nextInt();m = scanner.nextInt();int x = scanner.nextInt();int y = scanner.nextInt();int[][]array=new int[n+1][m+1];array[x][y]=0;LinkedList<Integer>hangQueue=new LinkedList<>();LinkedList<Integer>lieQueue=new LinkedList<>();// 使用这个数组 每次拿到一种x和y 避免手动枚举ifelseint[]dx={-2,-2,2,2,1,-1,1,-1};int[]dy={-1,1,-1,1,2,-2,-2,2};hangQueue.offer(x);lieQueue.offer(y);while(!hangQueue.isEmpty()){// 记录下一层元素个数Integer xx = hangQueue.poll();Integer yy = lieQueue.poll();for (int i = 0; i < 8; i++) {// 8种选择方式int  nextX= xx + dx[i];int nextY = yy + dy[i];if (nextX>=1 && nextX<=n && nextY>=1 && nextY<=m && array[nextX][nextY]==0){// 这个点可以走 步数等于走到这个点的步数+1array[nextX][nextY]=array[xx][yy]+1;hangQueue.offer(nextX);lieQueue.offer(nextY);}}}// 这个初始点值为0 可能再后期又被来过 再次赋值为0array[x][y]=0;for (int i = 1; i < array.length; i++) {for (int j = 1; j < array[i].length; j++) {if (array[i][j]==0 && (i!=x || j!=y)){System.out.print(-1+" ");}else{System.out.print(array[i][j]+" ");}}System.out.println();}}}

在赋值步数时，也可以使用层次的方式赋值，每次统计该层添加的个数，下次循环该个数即可拿到每层的元素

package SouSuo;import java.util.LinkedList;
import java.util.Scanner;public class P1443 {public static int n;public static int m;public static void main(String[] args) {Scanner scanner=new Scanner(System.in);n = scanner.nextInt();m = scanner.nextInt();int x = scanner.nextInt();int y = scanner.nextInt();int[][]array=new int[n+1][m+1];array[x][y]=0;LinkedList<Integer>hangQueue=new LinkedList<>();LinkedList<Integer>lieQueue=new LinkedList<>();int[]dx={-2,-2,2,2,1,-1,1,-1};int[]dy={-1,1,-1,1,2,-2,-2,2};hangQueue.offer(x);lieQueue.offer(y);int number=1;int count=0;while(!hangQueue.isEmpty()){// 记录下一层元素个数int geshu=0;count++;for (int j = 0; j < number; j++) {Integer xx = hangQueue.poll();Integer yy = lieQueue.poll();for (int i = 0; i < 8; i++) {// 8种选择方式int  nextX= xx + dx[i];int nextY = yy + dy[i];if (nextX>=1 && nextX<=n && nextY>=1 && nextY<=m && array[nextX][nextY]==0){// 这个点可以走 步数等于走到这个点的步数+1array[nextX][nextY]=count;hangQueue.offer(nextX);lieQueue.offer(nextY);geshu++;}}}number=geshu;}array[x][y]=0;for (int i = 1; i < array.length; i++) {for (int j = 1; j < array[i].length; j++) {if (array[i][j]==0 && (i!=x || j!=y)){System.out.print(-1+" ");}else{System.out.print(array[i][j]+" ");}}System.out.println();}}}

3 多方向搜索 

3.1 P1101 单词方阵

思路：

  • 在这个n×n的方阵里搜索一个单词，该单词摆放时有8种方向，即搜索时有8个方向
  • 关键点
    • 定义dx，dy数组列举出每个方向x，y的变化值
    • 搜索触发条件为碰到 'y' 这个字母时
  • 细节：
    • 因为有公用单词的存在，在标记这个单词时不能直接将这个字符转为'*'
    • 每一次变化dx，dy，在搜索时使用int L变量记录变化个数，实现数组索引的移动
package SouSuo;import java.util.Scanner;public class P1101 {public static int[]dx={-1,1,0,0,1,-1,1,-1};public static int[]dy={0,0,-1,1,1,-1,-1,1};public static char[]yizhong={'y','i','z','h','o','n','g'};public static char[][]array;public static boolean[][]isChar;public static int n;public static void main(String[] args) {Scanner scanner=new Scanner(System.in);n = scanner.nextInt();array=new char[n][n];scanner.nextLine();for (int i = 0; i < n; i++) {array[i]=scanner.nextLine().toCharArray();}isChar=new boolean[n][n];for (int i = 0; i < array.length; i++) {for (int j = 0; j < array[i].length; j++) {if (array[i][j]=='y'){dfs(i,j);}}}for (int i = 0; i < array.length; i++) {for (int j = 0; j < array[i].length; j++) {if (isChar[i][j]){System.out.print(array[i][j]);}else{System.out.print('*');}}System.out.println();}}/*** 搜索8个方向* @param i* @param j*/public static void dfs(int i, int j) {for (int k = 0; k < 8 ; k++) {int xx= dx[k];int yy= dy[k];int l;for (l= 1; l < 7; l++) {// 从当前位置向后找7个字符 判断是否相等int xxx = i + xx*l;int yyy = j + yy*l;if (xxx<0 || xxx>n-1 || yyy<0 || yyy>n-1){break;}if (array[xxx][yyy]!=yizhong[l]){break;}}if (l==7){for (l= 0; l < 7; l++) {int xxx = i + xx*l;int yyy = j + yy*l;isChar[xxx][yyy]=true;}}}}
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/19944.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

响应式布局学习笔记

响应式布局学习笔记

什么是响应式布局&#xff1f; 响应式布局&#xff08;Responsive Web Design&#xff09;是一种网页设计方法&#xff0c;使网站能够根据设备屏幕尺寸&#xff08;如手机、平板、电脑&#xff09;自动调整内容和布局&#xff0c;提供最佳浏览体验。 如何调试响应式布局&…
阅读更多...
Cursor 与团队协作：提升团队开发效率

Cursor 与团队协作：提升团队开发效率

引言 在团队开发中&#xff0c;代码质量参差不齐、重复错误频发、代码审查耗时过长是制约效率的三大痛点。据 GitHub 调查&#xff0c;开发者平均每周花费 4.3 小时修复他人代码问题&#xff0c;而 60% 的合并请求&#xff08;PR&#xff09;因风格或低级错误被驳回。Cursor 作…
阅读更多...
rocketmq-netty通信设计-request和response

rocketmq-netty通信设计-request和response

1、NettyRemotingServer启动分析 org.apache.rocketmq.remoting.netty.NettyRemotingServer#start public void start() {this.defaultEventExecutorGroup new DefaultEventExecutorGroup(nettyServerConfig.getServerWorkerThreads(),new ThreadFactory() {private AtomicI…
阅读更多...
蓝桥杯之图

蓝桥杯之图

图&#xff1a; 对于图来说&#xff0c;重点在于之后的最短路径算法&#xff0c;这边简单做一下了解即可 代码&#xff1a; #include<iostream> #include<string> #include<vector> #include<list> #include<queue> using namespace std; clas…
阅读更多...
mysql 学习15 SQL优化，插入数据优化，主键优化，order by优化，group by 优化，limit 优化，count 优化，update 优化

mysql 学习15 SQL优化，插入数据优化，主键优化，order by优化，group by 优化，limit 优化，count 优化，update 优化

插入数据优化&#xff0c; insert 优化&#xff0c; 批量插入&#xff08;一次不超过1000条&#xff09; 手动提交事务 主键顺序插入 load 从本地一次插入大批量数据&#xff0c; 登陆时 mysql --local-infile -u root -p load data local infile /root/sql1.log into table tb…
阅读更多...
143，【3】 buuctf web [GYCTF2020]EasyThinking

143，【3】 buuctf web [GYCTF2020]EasyThinking

进入靶场 一开始那个题目名字就想到了框架 扫描目录 访问后自动下载了 找源码 <?php namespace app\home\controller;use think\exception\ValidateException; use think\facade\Db; use think\facade\View; use app\common\model\User; use think\facade\Request; use …
阅读更多...
数据守护者：备份文件的重要性及自动化备份实践

数据守护者：备份文件的重要性及自动化备份实践

在信息化社会&#xff0c;数据已成为企业运营和个人生活的重要组成部分。无论是企业的核心业务数据&#xff0c;还是个人的珍贵照片、重要文档&#xff0c;数据的丢失或损坏都可能带来无法估量的损失。因此&#xff0c;备份文件的重要性愈发凸显&#xff0c;它不仅是数据安全的…
阅读更多...
PHP支付宝--转账到支付宝账户

PHP支付宝--转账到支付宝账户

官方参考文档&#xff1a; ​https://opendocs.alipay.com/open/62987723_alipay.fund.trans.uni.transfer?sceneca56bca529e64125a2786703c6192d41&pathHash66064890​ 可以使用默认应用&#xff0c;也可以自建新应用&#xff0c;此处以默认应用来讲解【默认应用默认支持…
阅读更多...
vscode插件开发

vscode插件开发

准备 安装开发依赖 npm install -g yo generator-code 安装后&#xff0c;运行命令 yo code 运行 打开项目&#xff0c; 点击 vscode 调式 按 F5 或点击调试运行按钮 会打开一个新窗口&#xff0c;在新窗口按快捷键 CtrlShiftP &#xff0c;搜索 Hello World 选择执行 右下角出…
阅读更多...
win11安装wsl报错：无法解析服务器的名称或地址（启用wsl2）

win11安装wsl报错：无法解析服务器的名称或地址（启用wsl2）

1. 启用wsl报错如下 # 查看可安装的 wsl --install wsl --list --online此原因是因为没有开启DNS的原因&#xff0c;所以需要我们手动开启DNS。 2. 按照如下配置即可 Google的DNS&#xff08;8.8.8.8和8.8.4.4) 全国通用DNS地址 (114.114.114.114) 3. 运行以下命令来重启 WSL…
阅读更多...
mysql 存储空间增大解决方案

mysql 存储空间增大解决方案

一&#xff1a;查询数据库中表占比比较多的表 SELECT table_name AS "Tables", round(((data_length index_length) / 1024 / 1024), 2) AS "Size (MB)" FROM information_schema.tables WHERE table_schema "自己的数据库名"; …
阅读更多...
【MySQL】数据库基础库/表的操作数据类型详解

【MySQL】数据库基础库/表的操作数据类型详解

主页&#xff1a;醋溜马桶圈-CSDN博客 专栏&#xff1a;实战项目_醋溜马桶圈的博客-CSDN博客 gitee&#xff1a;mnxcc (mnxcc) - Gitee.com 目录 1.什么是数据库 2.主流数据库 3.基本使用 3.1 MySQL安装 3.2 连接服务器 3.3 服务器管理 3.4 服务器、数据库、表关系 3.5 …
阅读更多...
【kafka系列】消费者

【kafka系列】消费者

目录 获取消息 1. 消费者获取消息的流程逻辑分析 阶段一&#xff1a;消费者初始化 阶段二&#xff1a;分区分配与重平衡&#xff08;Rebalance&#xff09; 阶段三&#xff1a;消息拉取与处理 阶段四&#xff1a;偏移量提交 核心设计思想 2. 流程 关键点总结 常见参数…
阅读更多...
仿叮咚买菜鸿蒙原生APP

仿叮咚买菜鸿蒙原生APP

# DingdongShopping 这是一个原生鸿蒙版的仿叮咚买菜APP项目 鸿蒙Next发布至今已经有一年多的时间了&#xff0c;但有时候我们想要实现一些复杂的功能或者效果&#xff0c;在开发文档上查阅一些资料还是比较费时的&#xff0c;有可能还找不到我们想要的内容。而社会层面上分享…
阅读更多...
Linux 进程控制（进程创建，进程等待）

Linux 进程控制（进程创建，进程等待）

目录 进程创建 fork函数初识 fork函数返回值 写时拷贝 fork常规用法 fork调用失败的原因 进程终止 进程退出场景 进程退出码 进程常见退出方法 exit函数 _exit函数 return退出 return、exit和_exit之间的区别与联系 进程异常退出 进程等待 进程等待的必要性 获…
阅读更多...
ROS2下Rviz显示orbbec相机depth深度图

ROS2下Rviz显示orbbec相机depth深度图

ROS2下Rviz显示orbbec相机depth深度图 视频讲解 ROS2下Rviz显示orbbec相机depth深度图 在《ROS2下编写orbbec相机C package并Rviz显示》的基础上&#xff0c;继续添加depth图像的获取及显示 rgb_publisher_ this->create_publisher<sensor_msgs::msg::Image>("…
阅读更多...
算法——结合实例了解Minimax算法（极小化极大算法）

算法——结合实例了解Minimax算法（极小化极大算法）

计算机科学中最有趣的事情之一就是编写一个人机博弈的程序。有大量的例子&#xff0c;最出名的是编写一个国际象棋的博弈机器。但不管是什么游戏&#xff0c;程序趋向于遵循一个被称为Minimax算法&#xff0c;伴随着各种各样的子算法在一块。本篇将简要介绍 minimax 算法&#…
阅读更多...
场外个股期权下单后多久成交？场外个股期权对投资组合的影响

场外个股期权下单后多久成交？场外个股期权对投资组合的影响

对普通老板们而言&#xff0c;它如同精密手术刀——用得好可精准优化投资组合&#xff0c;用不好则可能伤及本金。记住两个关键&#xff1a;一是永远用"亏得起的钱"参与&#xff0c;二是把合约条款当"药品说明书"逐字研读。 场外个股期权下单后多久成交&am…
阅读更多...
SolidWorks C# How

SolidWorks C# How

目录 1.如何创建C#插件程序？ 2.插件程序需要继承的类是什么？ 3.如何创建C#.net WPF程序？ 4.WPF界面程序参考 5.如何获取类的框图 6.如何安装XCAD.net的 nuget包 7.如何扩展命令到菜单栏和工具栏 8.如何添加自定义面板 9.如何对文档管理进行编程 10.XCAD 开发solid…
阅读更多...
【Go并发编程】Goroutine 调度器揭秘：从 GMP 模型到 Work Stealing 算法

【Go并发编程】Goroutine 调度器揭秘：从 GMP 模型到 Work Stealing 算法

每天一篇Go语言干货&#xff0c;从核心到百万并发实战&#xff0c;快来关注魔法小匠&#xff0c;一起探索Go语言的无限可能&#xff01; 在 Go 语言中&#xff0c;Goroutine 是一种轻量级的并发执行单元&#xff0c;它使得并发编程变得简单高效。而 Goroutine 的高效调度机制是…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023