题意就不用多说了，开始想直接bfs+二分简化下做试试 果断超时，，然后不得不用状态压缩dp（其实一开始就想这样做的，15个点 每个点都能走多次 绝逼状态压缩dp）
先bfs跑每个关键点之间的做短路径 再二分起点的能量值 状态压缩dp来判断 不说了 AC吧！！！！！
#include<stdio.h>#include<string.h>#include<queue>#include<iostream>using namespace std;#define INF 0x3f3f3f3fint n,m;char map[20][20];int leap[20][20],cont,coord[20][3],sum,fir;int dis[20][20],mark[20][20],dp[1<<17][17];int dir[4][2]={0,1,0,-1,1,0,-1,0};struct node{int x,y,step;}a,b;int bfs(int k){ int i; a.x=coord[k][1]; a.y=coord[k][2]; a.step=0; queue<node>q; memset(mark,0,sizeof(mark)); mark[a.x][a.y]=1; q.push(a); while(!q.empty()) { b=q.front(); q.pop(); for(i=0;i<4;i++) { a.x=b.x+dir[i][0]; a.y=b.y+dir[i][1]; a.step=b.step+1; if(a.x<0||a.x>=n||a.y<0||a.y>=m) continue; if(map[a.x][a.y]==’D’) continue; if(mark[a.x][a.y]==0) { mark[a.x][a.y]=1; if(leap[a.x][a.y]>=0)dis[k][leap[a.x][a.y]]=dis[leap[a.x][a.y]][k]=a.step;q.push(a); } } } return 0; }int max(int a,int b){return a>b?a:b;}int deal(int s){memset(dp,-1,sizeof(dp));dp[1<<fir][fir]=s;int i,j;int k=(1<<(cont+1));for(i=1;i<k;i++){for(j=0;j<=cont;j++){if((i&(1<<j))==0) continue;if(dp[i][j]<0) continue;if((i&sum)==sum) return 1;for(int x=0;x<=cont;x++){if(x==j) continue;if((i&(1<<x))!=0) continue;if(dp[i][j]<dis[j][x]) continue;if(map[coord[x][1]][coord[x][2]]==’G’) dp[i|(1<<x)][x]=s;else{dp[i|(1<<x)][x]=max(dp[i|1<<x][x],dp[i][j]-dis[j][x]);}}}}return 0;}int main(){int i,j;while(~scanf("%d%d",&n,&m),n+m){for(i=0;i<n;i++)scanf("%s",map[i]);cont=-1;sum=0;for(i=0;i<n;i++)for(j=0;j<m;j++){leap[i][j]=-1;if(map[i][j]==’F’){coord[++cont][1]=i;coord[cont][2]=j;leap[i][j]=cont;fir=cont;sum+=(1<<cont);}else if(map[i][j]==’G’){coord[++cont][1]=i;coord[cont][2]=j;leap[i][j]=cont;}else if(map[i][j]==’Y’){coord[++cont][1]=i;coord[cont][2]=j;leap[i][j]=cont;sum+=(1<<cont);sum 表示所有需要关闭的开关和起点 的状态}}memset(dis,INF,sizeof(dis));for(i=0;i<=cont;i++){dis[i][i]=0;bfs(i);广搜找点之间的最短路}int left=0,right=300,mid;int flash=-1;while(left<right)二分枚举答案{mid=(left+right)/2;if(deal(mid)){right=mid;flash=mid;}else left=mid+1;}printf("%d\n",flash);}return 0;}
文画音，看似耳目所为，其实是内心世界的感受。
