【深度搜索】吃奶酪

2023-10-15 01:50
文章标签 搜索 深度 奶酪

本文主要是介绍【深度搜索】吃奶酪,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

【深度搜索】吃奶酪

题目

题目描述

房间里放着 n 块奶酪。一只小老鼠要把它们都吃掉,问至少要跑多少距离?老鼠一开始在 (0,0) 点处。

输入格式

在这里插入图片描述## 输出格式
一个数,表示要跑的最少距离,保留 2 位小数。

输入输出样例

输入 #1 复制
4
1 1
1 -1
-1 1
-1 -1
输出 #1 复制
7.41

说明/提示

1≤n≤15。

分析

我们从起点开始搜,每次往不同点走,每次走完与上次最小距离比,取最小距离。

注意:题目是实数,所以数据存放用double,
还要剪枝,如果还没走完所有点,就已经超过当前的最小距离,那就减掉。

其他在代码里有清楚注释。。。。。。。

代码

#include<iostream>
#include<cmath> 
#include<cstdio>
using namespace std;int n;
double a[20],b[20];  //各存放每个点的x , y; 注意是实数 
bool vis[20];    //点是否被访问过 double ans = 0x3f3f3f3f;//sqrt( (x1-x2)^2  + (y1-y2)^2 )
double dis(int x,int y){sqrt((a[x]-a[y])*(a[x]-a[y]) + (b[x]-b[y])*(b[x]-b[y]) );
}// dep 走了几个点,  f目前点位置,  s总的长度 
void dfs(int dep,int f,double s){//剪枝优化,如果当前的距离已经大于 目前走过的最短距离,那再走也没意义了 if(s > ans){return ;}//如果走到n个点, 取最小的距离 if(dep == n){ans = min(ans,s);return ;}//从每个点开始dfs,	for(int i=1;i<=n;i++){if(!vis[i]){vis[i] = true;dfs(dep+1,i,s+dis(f,i));		//dep+1,走过的点数加1 vis[i] = false;					//i,这次走的位置, }					//s+dis(f,i),上次的累加距离+目前位置f到下个位置i的距离 }	
}int main(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i]>>b[i];}//起点位置(0,0),从起点开始搜 a[0]=b[0]=0;dfs(0,0,0);printf("%.2lf",ans);return 0;
}

这篇关于【深度搜索】吃奶酪的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/214574

相关文章

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

Python 中的异步与同步深度解析(实践记录)

《Python中的异步与同步深度解析(实践记录)》在Python编程世界里,异步和同步的概念是理解程序执行流程和性能优化的关键,这篇文章将带你深入了解它们的差异,以及阻塞和非阻塞的特性,同时通过实际... 目录python中的异步与同步:深度解析与实践异步与同步的定义异步同步阻塞与非阻塞的概念阻塞非阻塞同步

Redis中高并发读写性能的深度解析与优化

《Redis中高并发读写性能的深度解析与优化》Redis作为一款高性能的内存数据库,广泛应用于缓存、消息队列、实时统计等场景,本文将深入探讨Redis的读写并发能力,感兴趣的小伙伴可以了解下... 目录引言一、Redis 并发能力概述1.1 Redis 的读写性能1.2 影响 Redis 并发能力的因素二、

最新Spring Security实战教程之表单登录定制到处理逻辑的深度改造(最新推荐)

《最新SpringSecurity实战教程之表单登录定制到处理逻辑的深度改造(最新推荐)》本章节介绍了如何通过SpringSecurity实现从配置自定义登录页面、表单登录处理逻辑的配置,并简单模拟... 目录前言改造准备开始登录页改造自定义用户名密码登陆成功失败跳转问题自定义登出前后端分离适配方案结语前言

Python使用DeepSeek进行联网搜索功能详解

《Python使用DeepSeek进行联网搜索功能详解》Python作为一种非常流行的编程语言,结合DeepSeek这一高性能的深度学习工具包,可以方便地处理各种深度学习任务,本文将介绍一下如何使用P... 目录一、环境准备与依赖安装二、DeepSeek简介三、联网搜索与数据集准备四、实践示例:图像分类1.

Redis 内存淘汰策略深度解析(最新推荐)

《Redis内存淘汰策略深度解析(最新推荐)》本文详细探讨了Redis的内存淘汰策略、实现原理、适用场景及最佳实践,介绍了八种内存淘汰策略,包括noeviction、LRU、LFU、TTL、Rand... 目录一、 内存淘汰策略概述二、内存淘汰策略详解2.1 ​noeviction(不淘汰)​2.2 ​LR

Python与DeepSeek的深度融合实战

《Python与DeepSeek的深度融合实战》Python作为最受欢迎的编程语言之一,以其简洁易读的语法、丰富的库和广泛的应用场景,成为了无数开发者的首选,而DeepSeek,作为人工智能领域的新星... 目录一、python与DeepSeek的结合优势二、模型训练1. 数据准备2. 模型架构与参数设置3

Java深度学习库DJL实现Python的NumPy方式

《Java深度学习库DJL实现Python的NumPy方式》本文介绍了DJL库的背景和基本功能,包括NDArray的创建、数学运算、数据获取和设置等,同时,还展示了如何使用NDArray进行数据预处理... 目录1 NDArray 的背景介绍1.1 架构2 JavaDJL使用2.1 安装DJL2.2 基本操

最长公共子序列问题的深度分析与Java实现方式

《最长公共子序列问题的深度分析与Java实现方式》本文详细介绍了最长公共子序列(LCS)问题,包括其概念、暴力解法、动态规划解法,并提供了Java代码实现,暴力解法虽然简单,但在大数据处理中效率较低,... 目录最长公共子序列问题概述问题理解与示例分析暴力解法思路与示例代码动态规划解法DP 表的构建与意义动

Go中sync.Once源码的深度讲解

《Go中sync.Once源码的深度讲解》sync.Once是Go语言标准库中的一个同步原语,用于确保某个操作只执行一次,本文将从源码出发为大家详细介绍一下sync.Once的具体使用,x希望对大家有... 目录概念简单示例源码解读总结概念sync.Once是Go语言标准库中的一个同步原语,用于确保某个操