题目链接:传送门
题目大意:给你一副n*m大小的图，'D'表示墙,'F'表示起点,'S'表示空地,'G'表示能源站,'Y'表示开关,一开始机器人处在'F'并有一个初始能量，每走一步会消耗一格能量
机器人需要在能量耗尽前经过所有'Y'至少一次,其中经过'G'可补满能量回初始值但每个'G'只能补一次，问至少需要几个能量才能达到要求。
题目思路:这个题感觉真的是很考验功底，集bfs，状态压缩DP，二分于一身，且实现细节不能马虎，实在是一道好题。
为什么说是状态压缩DP，You can assume that 1<=n,m<=15, and the sum of energy pools and power switches is less than 15.
从题意（每个点可以走多次）以及这句话可以看出这道题是用状态压缩DP，而解题关键是重新构造一副抽象图，把有效点抽离出来，而抽离点需要它们之间
的距离关系，这就需要bfs，最后就是二分枚举答案，取出最小值就是答案。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cmath> 5 #include <algorithm> 6 #include <cstring> 7 #include <stack> 8 #include <cctype> 9 #include <queue> 10 #include <string> 11 #include <vector> 12 #include <set> 13 #include <map> 14 #include <climits> 15 #define lson root<<1,l,mid 16 #define rson root<<1|1,mid+1,r 17 #define fi first 18 #define se second 19 #define seg int root,int l,int r 20 #define ping(x,y) ((x-y)*(x-y)) 21 #define mst(x,y) memset(x,y,sizeof(x)) 22 #define mcp(x,y) memcpy(x,y,sizeof(y)) 23 #define Min(x,y) (x<y?x:y) 24 #define Max(x,y) (x>y?x:y) 25 using namespace std; 26 #define gamma 0.5772156649015328606065120 27 #define MOD 1000000007 28 #define inf 0x3f3f3f3f 29 #define N 1000 30 #define maxn 1000050 31 typedef long long LL; 32 typedef pair<int,int> PII; 33 34 char pic[20][20]; 35 int dis[20][20]; ///bfs中所用数组,记录的是搜索的点到其它有效点之间的距离 36 int dp[1<<17][20]; ///状态压缩DP转移数组,二维表示最后到达的是第几个点 37 int xx[20],yy[20]; ///抽离有效点,把横纵坐标保存下来 38 int d[20][20]; ///有效点对之间的距离 39 int state,cnt,ss,n,m; ///cnt表示有效点个数,state表示符合题意条件的值(用于匹配答案) 40 int dir[4][2]={{0,-1},{0,1},{1,0},{-1,0}}; 41 42 void bfs(int s){ 43 queue<int>q; 44 q.push(xx[s]);q.push(yy[s]); 45 dis[xx[s]][yy[s]]=0; 46 while(!q.empty()){ 47 int x=q.front();q.pop(); 48 int y=q.front();q.pop(); 49 for(int i=0;i<4;++i){ 50 int _x=x+dir[i][0]; 51 int _y=y+dir[i][1]; 52 if(_x<1||_x>n||_y<1||_y>m||dis[_x][_y]!=inf||pic[_x][_y]=='D')continue; 53 dis[_x][_y]=dis[x][y]+1; 54 q.push(_x);q.push(_y); 55 } 56 } 57 } 58 59 void init(){ 60 state=0;cnt=0; 61 for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){ 62 if(pic[i][j]=='F'){ 63 xx[cnt]=i;yy[cnt]=j; 64 state|=(1<<cnt); 65 ss=cnt; 66 ++cnt; 67 } 68 else if(pic[i][j]=='G'){ 69 xx[cnt]=i;yy[cnt]=j; ///因为'G'可过可不过,所以不是绝对条件 70 ++cnt; 71 } 72 else if(pic[i][j]=='Y'){ 73 xx[cnt]=i;yy[cnt]=j; 74 state|=(1<<cnt); 75 ++cnt; 76 } 77 } 78 } 79 80 int check(int en){ 81 int all=1<<cnt; 82 mst(dp,-1); 83 dp[1<<ss][ss]=en; 84 for(int i=1<<ss;i<all;++i){ 85 for(int j=0;j<cnt;++j){ 86 if(!(i&(1<<j))||dp[i][j]<0)continue; ///i状态必须过j,后面操作才有意义 87 if((i&state)==state)return 1; ///符合绝对条件,该能量满足 88 for(int k=0;k<cnt;++k){ 89 if(j==k||(i&(1<<k)))continue; 90 dp[i|(1<<k)][k]=Max(dp[i|(1<<k)][k],dp[i][j]-d[j][k]); 91 if(pic[xx[k]][yy[k]]=='G'&&dp[i|(1<<k)][k]>=0) 92 dp[i|(1<<k)][k]=en; ///经过'G',能量回满 93 } 94 } 95 } 96 return 0; 97 } 98 99 int main(){ 100 //freopen("lxx.txt","r",stdin); 101 int i,j,x,y,v,group,Case=0; 102 while(scanf("%d%d",&n,&m)!=EOF&&(n||m)){ 103 mst(d,inf); 104 for(i=1;i<=n;++i)scanf("%s",pic[i]+1); 105 init(); 106 for(i=0;i<cnt;++i){ 107 mst(dis,inf); 108 bfs(i); 109 for(j=0;j<cnt;++j) 110 d[i][j]=dis[xx[j]][yy[j]]; 111 } 112 int l=1,r=4000,ans=inf; 113 while(l<=r){ 114 int mid=l+r>>1; 115 if(check(mid)){ans=mid;r=mid-1;} 116 else l=mid+1; 117 } 118 if(ans==inf)printf("-1 "); 119 else printf("%d ",ans); 120 } 121 return 0; 122 }