题目链接：
题解：看似有点下记忆话搜索但是由于他是能走8个方向的也就是说两点的距离其实就是最大的x轴或y轴的差。然后只有15个藏金点状压一下加dfs就行了。
#include#include #include #include #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;}