LightOJ1057 Collecting Gold 旅行商问题

题目

Finally you found the city of Gold. As you are fond of gold, you start collecting them. But there are so much gold that you are getting tired collecting them.

So, you want to find the minimum effort to collect all the gold.

You can describe the city as a 2D grid, where your initial position is marked by an ‘x’. An empty place will be denoted by a ‘.’. And the cells which contain gold will be denoted by ‘g’. In each move you can go to all 8 adjacent places inside the city.

问从x出发收集完所有黄金并回到x至少需要走多少步,每步可以选择8个方向中的一个.

题解

因为要从x出发,然后回到x,不难想到旅行商问题的方向.

然后就是构图,对我们有意义的是有g有x的点,我们可以把他们两两之间的距离算出来.这样就构成了一个完全图.

从一个点到另一个点的距离为$max(|x_1-x_2|,|y_1-y_2|)$

旅行商问题复杂度$O(n^2*2^n)$

代码

#include<cstdio>
#include<cstring>
#include<cstdlib>
#define min(a,b) (a<b?a:b)
#define max(a,b) ((a)>(b)?(a):(b))
const int MAXN=25;
const int INF=1e9+7;
char s[MAXN][MAXN];
int cost[MAXN][MAXN];
int x[MAXN],y[MAXN],tot;
int dp[MAXN][1<<16];
void init(){
    for(int i=0;i<tot;++i){
        for(int j=0;j<tot;++j){
            cost[i][j]=max(abs(x[i]-x[j]),abs(y[i]-y[j]));
        }
    }
}
int dfs(int now,int S){//到达now点,有S个黄金的最小步数
    if(dp[now][S]>=0)return dp[now][S];
	if(now==0&&S==0)return 0;
    dp[now][S]=INF;
    for(int i=0;i<tot;++i){
        int num=1<<i;
		//if(i==now)continue; 只有x没有g时,会出问题
        if((num&S)&&S>=num){
            dp[now][S]=min(dp[now][S],dfs(i,S-num)+cost[i][now]);
        }
    }
    return dp[now][S];
}
int main(){
    int T;scanf("%d",&T);
    for(int test=1;test<=T;++test){
        int N,M;scanf("%d%d",&N,&M);
        for(int i=0;i<N;++i)scanf("%s",s[i]);
        tot=0;
        for(int i=0;i<N;++i){
            for(int j=0;j<M;++j){
                if(s[i][j]=='g'||s[i][j]=='x'){
                    x[tot]=i;
                    y[tot++]=j;
                }
            }
        }
        init();
		memset(dp,-1,sizeof(dp));
        printf("Case %d: %d\n",test,dfs(0,(1<<tot)-1));
    }
    return 0;
}