lightoj 1057 - Collecting Gold（状压dp）

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

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

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cmath>

#define inf 0X3f3f3f3f

using 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;

}