dfs(学姐的红包）

链接：https://ac.nowcoder.com/acm/contest/3402/I

   盼啊，盼啊，伴随着时钟的敲响，我们即将迎来了美好的传统佳节-春节。为了给新年增添浓浓节日气息，师弟师妹们纷纷向师姐说：“师姐我想要收大红包！”，而我们人美心善声音靓的jx师姐也很大气地说：“给，给大个的，n个够吗？”，师弟师妹：“够了，谢谢师姐，师姐真好。”，但是可爱调皮的师姐将总共n个红包给藏在了实验室228里，并给了你每个红包的坐标。机智的你当然是得拿走所有红包，但是你得移动最少的距离来拿到所有红包!!奥里给!!一开始你在(0,0)处。

输入描述:

第一行包含一个整数n（0<=n<=13)

接下来n行，每行2个实数，

表示第i个红包的坐标x,y(0<=|x|,|y|<=30)

两点之间的距离公式为

sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));

输出描述:

需要走的最少距离，结果保留小数点后2位。

示例1

输入

2
-1 1
2 2

输出

4.58

解题思路：因为数据范围不大所以可以用dfs暴搜
AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
inline int read() {int x=0,f=1;char c=getchar();while(c!='-'&&(c<'0'||c>'9'))c=getchar();if(c=='-')f=-1,c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return f*x;}
typedef long long ll;
const int maxn = 1e2+10;
double x[maxn];
double y[maxn];
double ans=1000000.0;
int vis[maxn];
double dis[maxn][maxn];
int n;
void dfs(int x,int now,double min1){//x是深度，now是现在的状态因为你要从上一状态继续走//min1记录最小值 
    if(min1>ans){
        return ;
    }
    if(x==n){
        ans=min1;
    }
    for(int i=1;i<=n;i++){
        if(vis[i]==0){
            vis[i]=1;//标记数组
            dfs(x+1,i,min1+dis[i][now]);
            vis[i]=0;
        }
    }
}
int main()
{

    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x[i]>>y[i];
    }
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            dis[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));//先算出打表算出任意两点的距离
        }
    }
    dfs(0,0,0.0);
    printf("%.2lf",ans);
    return 0;
}

View Code

AC代码2：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
inline int read() {int x=0,f=1;char c=getchar();while(c!='-'&&(c<'0'||c>'9'))c=getchar();if(c=='-')f=-1,c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return f*x;}
typedef long long ll;
const int maxn = 1e2+10;
double x[maxn],y[maxn];
double lmin=1000000.0;
double dis(int i,int j){
    return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}
int vis[maxn];
int p[maxn];
int n;
void dfs(int x,double ans){
    if(ans>lmin)return;
    if(x==n){
        lmin=ans;
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            vis[i]=1;
            p[x]=i;
            dfs(x+1,ans+dis(p[x],p[x-1]));//p[x-1]是上一个状态
            vis[i]=0;
        }
    }

}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x[i]>>y[i];
    }
    dfs(0,0.0);
    printf("%.2lf",lmin);
    return 0;
}

View Code