首页 > 代码库 > BestCoder14 1002.Harry And Dig Machine（hdu 5067） 解题报告
BestCoder14 1002.Harry And Dig Machine（hdu 5067） 解题报告
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5067
题目意思：给出一个 n * m 的方格，每一个小方格（大小为1*1）的值要么为 0 要么为一个正整数。规定是正整数的值得方格个数不超过 10 个。现在问从最左上角的点开始，要经过所有正整数的值的点之后，要返回到最左上角的点的最短路径是多少。
其实为正整数的那些点具体值是什么根本无关紧要。可以先求出所有点到其他点的两两最短路径，然后利用状态压缩 （考虑到只有10个点，状态数最多为2^10）来求出答案），题解是这样说的：
dp[i][j]：表示状态 i 的点被访问过了，当前停留在点 j 需要的最少时间。枚举另一个不在状态 i 内的点 k ， 从点 j 走到点 k 的状态转移方程为：
dp[i|(1<<k)][k] = min(dp[i|(1<<k)][k], dp[i][j] + dist(j, k))
其中，dist[j][k] 表示从点 j 与 点 k 的最短距离。所以可以利用 bfs（当然有更简单的解法，这里我是为了练手而已） 求出以每一个点作为出发点，求出以这个点到其他所有点的最短距离。
代码中的 dp 计算，和方程有一点点不同。有些地方不太理解，先留着吧。。。
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cstring> 4 #include <iostream> 5 #include <algorithm> 6 #include <queue> 7 using namespace std; 8 9 const int maxn = 50 + 5; 10 const int INF = 0x3f3f3f3f; 11 int n, m, cnt, st[maxn], end[maxn]; 12 int vis[maxn][maxn], hs[maxn][maxn]; 13 int dp[maxn][1<<13], dist[maxn][maxn]; 14 15 int dx[] = {0, 1, 0, -1}; 16 int dy[] = {1, 0, -1, 0}; 17 18 struct node 19 { 20 int x, y; 21 int step; 22 } cur, tmp; 23 24 queue<node> q; 25 26 void bfs(int id) 27 { 28 while (!q.empty()) 29 q.pop(); 30 memset(vis, 0, sizeof(vis)); 31 tmp.x = st[id], tmp.y = end[id]; 32 tmp.step = dist[id][id] = 0; 33 q.push(tmp); 34 vis[st[id]][end[id]] = 1; 35 36 while (!q.empty()) 37 { 38 tmp = q.front(); 39 q.pop(); 40 41 for (int i = 0; i < 4; i++) 42 { 43 int tx = tmp.x + dx[i]; 44 int ty = tmp.y + dy[i]; 45 if (tx >= 1 && tx <= n && ty >= 1 && ty <= m && !vis[tx][ty]) 46 { 47 vis[tx][ty] = 1; 48 cur.x = tx; 49 cur.y = ty; 50 cur.step = tmp.step + 1; 51 if (hs[tx][ty] != -1) // the target point‘s id 52 dist[id][hs[tx][ty]] = cur.step; 53 q.push(cur); 54 } 55 } 56 } 57 } 58 59 void Init() 60 { 61 memset(hs, -1, sizeof(hs)); 62 int val; 63 cnt = 0; 64 for (int i = 1; i <= n; i++) 65 { 66 for (int j = 1; j <= m; j++) 67 { 68 scanf("%d", &val); 69 if (val || i == 1 && j == 1) 70 { 71 st[cnt] = i; 72 end[cnt] = j; 73 hs[i][j] = cnt++; // 为每一个大于0的点（最多只有10个）编号，第一个点编号为0而不是1 74 } 75 } 76 } 77 } 78 79 int main() 80 { 81 #ifndef ONLINE_JUDGE 82 freopen("in.txt", "r", stdin); 83 #endif 84 85 while (scanf("%d%d", &n, &m) != EOF) 86 { 87 Init(); 88 for (int i = 0; i < cnt; i++) // the shortest path from point i to other points 89 bfs(i); 90 int status = 1<<cnt; 91 memset(dp, 0x3f, sizeof(dp)); 92 93 dp[0][0] = 0; 94 for (int i = 0; i < status; i++) 95 { 96 for (int j = 0; j < cnt; j++) 97 { 98 if (dp[j][i] != INF) 99 {100 for (int k = 0; k < cnt; k++)101 {102 if (!(i & (1<<k))) // 点k不包含在状态i上103 dp[k][i|(1<<k)] = min(dp[k][i|(1<<k)], dp[j][i]+dist[j][k]);104 }105 }106 }107 }108 printf("%d\n", dp[0][status-1]);109 }110 return 0;111 }
代码中最后的输出 dp[0][status-1] 很明显就是从最左上角的点出发，经过所有正整数点的最短距离。不过为什么求得时候与二维数组dp[][]不同，这个确实不太理解。
BestCoder14 1002.Harry And Dig Machine（hdu 5067） 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。