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

题解：看似有点下记忆话搜索但是由于他是能走8个方向的也就是说两点的距离其实就是最大的x轴或y轴的差。然后只有15个藏金点状压一下加dfs就行了。

#include <iostream>#include <cstring>#include <cstdio>#include <cmath>#define inf 0X3f3f3f3fusing namespace std;char mmp[30][30];struct TnT {    int x , y;}Node[20];int getlen(int x , int y) {    return max(abs(Node[x].x - Node[y].x) , abs(Node[x].y - Node[y].y));}int dp[17][1 << 17] , cnt;void dfs(int pos , int state) {    if(state == (1 << cnt) - 1) return ;    for(int i = 0 ; i < cnt ; i++) {        if(state & (1 << i)) continue;        else {            if(dp[i][state | (1 << i)] > dp[pos][state] + getlen(pos , i)) {                dp[i][state | (1 << i)] = dp[pos][state] + getlen(pos , i);                dfs(i , state | (1 << i));            }        }    }}int main() {    int t;    scanf("%d" , &t);    int n , m , Case = 0;    while(t--) {        scanf("%d%d" , &n , &m);        int count = 0;        for(int i = 0 ; i < n ; i++) {            scanf("%s" , mmp[i]);            for(int j = 0 ; j < m ; j++) {                if(mmp[i][j] == ‘x‘) Node[0].x = i , Node[0].y = j;                if(mmp[i][j] == ‘g‘) Node[++count].x = i , Node[count].y = j;            }        }        for(int i = 0 ; i <= count ; i++) {            for(int j = 0 ; j < (1 << count + 1) ; j++) {                dp[i][j] = inf;            }        }        cnt = count + 1;        dp[0][0] = 0;        dfs(0 , 0);        int ans = inf;        for(int i = 1 ; i <= count ; i++) {            ans = min(ans , dp[i][(1 << cnt) - 1] + getlen(0 , i));        }        printf("Case %d: %d\n" , ++Case , ans == inf ? 0 : ans);    }    return 0;}

lightoj 1057 - Collecting Gold（状压dp）