欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【深度搜索】吃奶酪

程序员文章站 2022-05-24 08:48:57
...

【深度搜索】吃奶酪

题目

题目描述

房间里放着 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;
}
相关标签: # 深度搜索