首页 > 代码库 > lightoj1057_状压dp

lightoj1057_状压dp

题目链接:http://lightoj.com/volume_showproblem.php?problem=1057

题目大意:在二维矩阵中,给你一个起点和至多15个的目标点。要你求出从起点出发经过完所有的点后回到起点的最短路径值。每个点一步可以向 八个方向走。

没有金子的时候特判

 1 #include <algorithm> 2 #include <iostream> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cstdio> 6 #include <vector> 7 #include <ctime> 8 #include <queue> 9 #include <list>10 #include <cmath>11 #include <set>12 #include <map>13 using namespace std;14 #define INF 0x3f3f3f3f15 typedef long long LL;16 17 char s[25][25];18 int x[20], y[20], dp[1<<15][20];19 int Distance(int a, int b)20 {21     return max(fabs(y[b]-y[a]), fabs(x[b]-x[a]));22 }23 int main()24 {25     int t, n, m;26     scanf("%d", &t);27     for(int ca = 1; ca <= t; ca++)28     {29         scanf("%d %d", &n, &m);30         for(int i = 0; i < n; i++)31             scanf("%s", s[i]);32         int k = 0;33         for(int i = 0; i < n; i++)34             for(int j = 0; j < m; j++)35                 if(s[i][j]==x)36                     x[0] = i, y[0] = j;37                 else if(s[i][j] == g)38                 {39                     k++;40                     x[k] = i, y[k] = j;41                 }42         if(k == 0)43         {44             printf("Case %d: 0\n", ca);45             continue;46         }47         memset(dp, INF, sizeof(dp));48         for(int i = 0; i < k; i++)49             dp[1<<i][i+1] = Distance(0, i+1);50         for(int i = 2; i <= k; i++)51         {52             for(int j = 1; j < (1<<k); j++)53             {54                 int te = j, Zero[20], yi[20], l0=0, l1=0;55                 for(int l = 0; l < k; l++)56                 {57                     if(te % 2)58                         yi[++l1] = l;59                     else60                         Zero[++l0] = l;61                     te >>= 1;62                 }63                 if(l1 != i - 1)64                     continue;65                 for(int d0 = 1; d0 <= l0; d0++)66                 {67                     int k0 = Zero[d0];68                     for(int d1 = 1; d1 <= l1; d1++)69                     {70                         int k1 = yi[d1];71                         if(dp[j][k1+1] != INF)72                             dp[j|(1<<k0)][k0+1] = min(dp[j|(1<<k0)][k0+1], dp[j][k1+1]+Distance(k0+1, k1+1));73                     }74                 }75             }76         }77         int res = INF;78         for(int i = 1; i <= k; i++)79         {80             dp[(1<<k)-1][i] += dp[1<<(i-1)][i];81             res = min(dp[(1<<k)-1][i], res);82         }83         printf("Case %d: %d\n", ca, res);84     }85     return 0;86 }

 

lightoj1057_状压dp