1057 - Collecting Gold (状态压缩DP)

题目大意:
给你一个矩阵,'x'是你的起始位置, 'g'是宝藏的位置,问最少多少步可以把所有的宝藏取完,并且最后返回起始位置。
注意:没有宝藏的时候输出 0
 
====================================================================================
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<map>
using namespace std;
typedef long long LL;
const int INF = 1e9+;
const int MAXN = ;
int dp[MAXN][], m, n, k;///状态,当前所在的位置
char maps[][];
struct Point
{
int x, y;
}P[], Star; int GetLen(Point A, Point B)
{
int len = min(abs(A.x-B.x),abs(A.y-B.y));
len += max(abs(A.x-B.x),abs(A.y-B.y)) - len;
return len;
} int DFS(int sta,int x)///状态, 现在所在的位置
{
if(dp[sta][x] != -) return dp[sta][x]; dp[sta][x] = INF;
for(int i=; i<k; i++)
{
if( (sta&(<<i)) && i != x)
{
dp[sta][x] = min(dp[sta][x], DFS(sta-(<<x), i)+GetLen(P[x],P[i]));
}
}
// printf("dp[%d][%d] = %d\n", sta, x, dp[sta][x]);
return dp[sta][x];
} int main()
{
int T, cas = ;
scanf("%d", &T);
while(T --)
{
scanf("%d %d",&n, &m);
k = ;
memset(dp, -, sizeof(dp));
for(int i=; i<n; i++)
{
scanf("%s", maps[i]);
for(int j=; j<m; j++)
{
if(maps[i][j] == 'g')
P[k].x = i, P[k++].y = j;
if(maps[i][j] == 'x')
Star.x = i, Star.y = j;
}
} for(int i=; i<k; i++)
{
int sta = <<i;
dp[sta][i] = GetLen(Star, P[i]);
} int ans = INF, Lim = (<<k)-;
for(int i=; i<k; i++)///最后停留的位置
ans = min(ans,DFS(Lim,i)+GetLen(Star,P[i]));
if(k == )
ans = ;
printf("Case %d: %d\n", cas ++, ans);
}
return ;
}
上一篇:Purpose of requirePermission attribute (web.config)


下一篇:TCP/IP详解学习笔记(14)-TCP连接的未来和性能(未写完)