MYF

HDU 5067 Harry And Dig Machine

Posted on | In | | Visitors

题目链接

HDU 5067

题目类型：状态压缩dp

题目分析

题目大意

$n*m$的矩阵，任意相邻（左右／上下）两个点的距离为一，问把所有不为零的点全跑一遍的最短距离。

解析

因为只有最多只有十个点，所以想到了暴力跑的方法。对于一个点DFS，然后标记，然后访问下一级中没有访问的，直到所有都访问了，然后再回溯把标记去掉，相当于跑了10层for循环，很显然这个是会T掉的。所以在这里考虑使用状压DP，如何压缩状态呢？比如当我跑到第二层的5 4 3 2 1和4 5 3 2 1，那么3 2 1有三种情况，以3结尾，以2结尾，以1结尾，所以第一维使用二进制的思想，第二维使用位数来新建数组。这样如果算最终的结果，只需要取二进制位全都取过的，对应的十进制数字就是(2^len-1)，以0结尾的数，即dp[2^len-1][0]就是结果。

某神奇的小伙伴竟然使用next_permutation过了，时间复杂度高了一点。

状压DP参考题解: hdu 5067 Harry And Dig Machine(状态压缩dp）

代码

next_permutation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <climits>
#include <string>
#include <stdlib.h>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <deque>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1)
#define rt(n)       (i == n ? '\n' : ' ')
#define hi         printf("Hi----------\n")
#define IN freopen("input.txt","r",stdin);
#define OUT freopen("output.txt","w",stdout);
#define pii pair<int,int>
#define debug(x) cout<<"Debug : ---"<<x<<"---"<<endl;
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long ll;
using namespace std;
const int maxn=10000+5;
const int mod=1000000007;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
struct Point{
    int x,y;
}p[15];
int vis[15],cnt,dp[1<<12][15];
bool cmp(Point a,Point b){
    if (a.x==b.x) {
        return a.y<b.y;
    }
    else
        return a.x<b.x;
}
int main(){
    int n,m,tmp;
    while (scanf("%d%d",&n,&m)!=EOF) {
        cnt=0;
        for (int i=1; i<=n; i++) {
            for (int j=1; j<=m; j++) {
                scanf("%d",&tmp);
                if (tmp!=0) {
                    p[cnt].x=i-1;
                    p[cnt++].y=j-1;
                }
            }
        }
        
        int ans=INF;
        do{
            tmp = p[0].x + p[0].y;
            for (int i=1; i<cnt; i++) {
                tmp+= abs(p[i].x-p[i-1].x)+abs(p[i].y-p[i-1].y);
            }
            tmp += p[cnt-1].x + p[cnt-1].y;
            ans = min(ans, tmp);
            
        }while (next_permutation(p, p+cnt, cmp)) ;
    //AKKKA
        cout<<ans<<endl;
    }
}

状压DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <deque>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1)
#define pb push_back
#define mp make_pair
#define rt(n)       (i == n ? '\n' : ' ')
#define hi         printf("Hi----------\n")
#define IN freopen("input.txt","r",stdin);
#define OUT freopen("output.txt","w",stdout);
#define debug(x) cout<<"Debug : ---"<<x<<"---"<<endl;
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int maxn=100000+5;
const int mod=1000000007;
const int INF=0x3f;
const double eps=1e-8;
int dp[(1<<12)+10][12];
int dis[12][12];
vector<PII>v;
int main(){
    int n,m,tmp;
    while (scanf("%d%d",&n,&m)!=EOF) {
        v.clear();
        for (int i=1; i<=n; i++) {
            for (int j=1; j<=m; j++) {
                scanf("%d",&tmp);
                if (tmp) {
                    if (i==1&&j==1) {
                        continue;
                    }
                    v.pb(mp(i,j));
                }
            }
        }
      
        if (v.size()==0) {
            printf("0\n");
            continue;
        }
        
        Memset(dis, 0);
        for (int i=0; i<v.size(); i++) {
            dis[i+1][0] = dis[0][i+1] = v[i].first + v[i].second -2;
        }
        for (int i=0; i<v.size(); i++) {
            for (int j=0; j<v.size(); j++) {
                dis[i+1][j+1] = abs(v[i].first-v[j].first)+abs(v[i].second-v[j].second);
                dis[j+1][i+1] = abs(v[i].first-v[j].first)+abs(v[i].second-v[j].second);
            }
        }
        
        Memset(dp, INF);
        int len = v.size() + 1;
        int total = 1<<len;
        for (int i=0; i<len; i++) {
            dp[1<<i][i] = dis[0][i];
        }
        for (int i=0; i<total; i++) {
            for (int j=0; j<len; j++) {
                if ((i>>j)&1) {
                    for (int k=0; k<len; k++) {
                        if (j==k) {
                            continue;
                        }
                        if ((i>>k)&1) {
                            dp[i][j] = min(dp[i][j], dp[i-(1<<j)][k]+ dis[k][j]);
                        }
                    }
                }
            }
        }
        
        cout<<dp[total-1][0]<<endl;
    }
}