//??[9/19/2014?Sjm] /* dis[j][k]?:=?從?j?點(diǎn)到?k?點(diǎn)的最少步數(shù)，由于They?can?travel?in?all?8?adjacent?direction?in?one?step.故而?dis[j][k]?=?max(?abs(Xj?-?Xk),?abs(Yj?-?Yk)?)f[j][i]?:=?在?i?狀態(tài)下，最后收集堅(jiān)果?j?的最少步數(shù)n?代表堅(jiān)果的數(shù)目。。階段i：按遞增順序枚舉狀態(tài)值?(0?<=?i?<=?2^n?-?1) 狀態(tài)?：枚舉狀態(tài)?i?中最后被收集的堅(jiān)果?j?（1?<=?j?<=?n,?i&(2^(j-1))?!=?0） 決策?：枚舉狀態(tài)?i?以外的堅(jiān)果?k（1?<=?k?<=?n,?i&(2^(k-1))?==?0）?,判斷在狀態(tài)?i，最后被收集的堅(jiān)果為j的情況下，再收集堅(jiān)果?k?,是否為最優(yōu)決策。即：?f[k][i+2^(k-1)]?=?min(f[k][i+2^(k-1)],?f[j][i]?+?dis[j][k])求最終解： 枚舉?f[j][2^n?-?1]?+?dis[j][0]?(1?<=?j?<=?n), */
1 #include <iostream> 2 #include <cstdlib> 3 #include <cstdio> 4 #include <algorithm> 5 #define INF 0x3f3f3f3f 6 using namespace std; 7 int n, dis[20][20], myX, myY, f[20][(1 << 20)]; 8 9 struct myNode { 10 int x, y; 11 }node[20]; 12 13 void Init(int i, char str[]) 14 { 15 for (int j = 0; j < myY; ++j){ 16 if ('#' == str[j]) { 17 node[++n].x = i; 18 node[n].y = j; 19 } 20 else if ('L' == str[j]) { 21 node[0].x = i; 22 node[0].y = j; 23 } 24 } 25 } 26 27 void getDis() { 28 for (int i = 0; i <= n; ++i) { 29 for (int j = 0; j <= n; ++j) { 30 dis[i][j] = max(abs(node[i].x - node[j].x), abs(node[i].y - node[j].y)); 31 } 32 } 33 } 34 35 void Solve() { 36 int finalState = (1 << n) - 1; 37 for (int j = 1; j <= n; ++j) { 38 for (int i = 0; i <= finalState; ++i) { 39 f[j][i] = INF; 40 } 41 } 42 for (int j = 1; j <= n; ++j) { 43 f[j][1 << (j - 1)] = dis[0][j]; 44 } 45 for (int i = 0; i < finalState; ++i) { 46 for (int j = 1; j <= n; ++j) { 47 if (i & (1 << (j - 1))) { 48 for (int k = 1; k <= n; ++k) { 49 if (!(i & (1 << (k - 1)))) { 50 f[k][i + (1 << (k - 1))] = min(f[k][i + (1 << (k - 1))], f[j][i] + dis[j][k]); 51 } 52 } 53 } 54 } 55 } 56 int ans = INF; 57 for (int j = 1; j <= n; ++j) { 58 ans = min(ans, f[j][finalState] + dis[j][0]); 59 } 60 printf("%d\n", ans); 61 } 62 63 int main() 64 { 65 while (~scanf("%d %d", &myX, &myY)) { 66 char str[25]; 67 n = 0; 68 for (int i = 0; i < myX; ++i) { 69 scanf("%s", str); 70 Init(i, str); 71 } 72 if (0 == n) { // 注意無(wú)堅(jiān)果的情況。。 73 printf("0\n"); 74 continue; 75 } 76 getDis(); 77 Solve(); 78 } 79 return 0; 80 }

轉(zhuǎn)載于:https://www.cnblogs.com/shijianming/p/4140800.html

總結(jié)

以上是生活随笔為你收集整理的状态压缩 之 UVA 10944 - Nuts for nuts..的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。