BestCoder Round #14 B 题 Harry And Dig Machine 【TSP】

柔情只为你懂 2022-08-13 11:38 106阅读 0赞

题目：[Harry And Dig Machine ][Harry And Dig Machine]

哈哈 终于涨边粉色了，不容易呀。顺便写一道题解吧

题意：给一个m\*n的矩阵，然后其中最多由10个有值，求总左上角把所有的值都拿上回到左上角的最小步数。

标准的TSP回到原点问题，需要先预处理出图来，然后TSP即可。

AC代码：

#include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <string>
    #include <iostream>
    #include <vector>
    #include <cmath>
    using namespace std;
    const int inf = 0x3f3f3f3f;
    const int N = 15;
    int mp[N][N];
    struct Node
    {
        int x,y;
    };
    vector<Node> vv;
    int n,m;
    int dp[1<<N][N];
    int main()
    {
        while(~scanf("%d%d",&n,&m))
        {
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<m;j++){
                    int x;
                    scanf("%d",&x);
                    if(x)
                        vv.push_back((Node){i,j});
                }
            }
            int okk = 0;
            for(int i=0;i<vv.size();i++)
            {
                if(vv[i].x==0 && vv[i].y==0)
                {
                    okk=1;
                    continue;
                }
            }
            if(okk==0)
                vv.push_back((Node){0,0});
            for(int i=0;i<vv.size();i++)
            {
                for(int j=0;j<vv.size();j++)
                {
                    mp[i][j] = 0;
                    if(i==j)
                        continue;
                    mp[i][j] = abs(vv[i].x-vv[j].x) + abs(vv[i].y-vv[j].y);
                }
            }
            int len = vv.size();
            n = len;
            for(int st=0;st<(1<<n);st++)  //TSP
            {
                for(int i=0;i<n;i++)
                {
                    if((st&(1<<i))==0)  //Ϊ0
                        continue;
                    if(st==(1<<i)){
                        dp[st][i]=mp[0][i];continue;
                    }
                    dp[st][i]=inf;
                    for(int j=0;j<n;j++)
                    {
                        if((st&(1<<j)) && i!=j)//Ϊ1
                        {
                            dp[st][i]=min(dp[st&~(1<<i)][j]+mp[j][i],dp[st][i]);
                        }
                    }
                }
            }
            int ans=inf;
            for(int i=0;i<n;i++){
                ans=min(ans,dp[(1<<n)-1][i]+mp[i][0]);
            }
            printf("%d\n",ans);
            vv.clear();
        }
        return 0;
    }

[Harry And Dig Machine]: http://acm.hdu.edu.cn/showproblem.php?pid=5067