BestCoder14 1002.Harry And Dig Machine（hdu 5067）解题报告

浏览数：27 / 时间：2015年06月20日

题目链接：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 }