首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。