题意：
给一个n*m的矩阵，每个格子中有一个大写字母，一个机器人从‘F’出发，拾取所有的开关‘Y’时便能够越狱，但是每走一格需要花费1点能量，部分格子为充电站‘G’，每个电站只能充1次电。而且部分格子为障碍'D'或者空格‘S’。机器人在开始时电池是满能量的，问电池容量至少为多少可以越狱？（1<=n,m<=14，充电站+开关的总个数<=15）
思路：
看错题了，以为充电站和开关的个数分别至多为14，其实是两种加起来14。
既然只有15个关键的格子，那么状压就有用了。假设每个点关键格必须走1次，那么就像可重复走的TSP了。但是充电站只能充1次，而且路过了也可以不充。所以，其实关键格只有那些“开关”，只要保证所有开关都收集全了，其他都无所谓。
具体做法，求出这15个格子（包括起点）的两两之间的距离（BFS就够了），相当于一个完全连通图。再二分答案，判断是否能够收集所有开关。判断能否收集开关，就相当于求所有点只能走1次的欧拉路径了，直接状态压缩来求，注意：两点间不一定可达，遇到充电站必须充满电。这样子对于一个格子具体走过了多少格已经没有关系了。
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <deque>
#include <map>
#include <algorithm>
#include <vector>
#include <iostream>
#define pii pair<int,int>
#define INF 0x3f3f3f3f
#define LL long long
#define ULL unsigned long long
using namespace std;
const double PI = acos(-1.0);
const int N=;
int dp[<<][N], tag[N][N], vis[N][N], dis[N][N], n, m, egy;
char g[N][N]; struct node
{
int x,y,d;
node(){};
node(int x,int y,int d):x(x),y(y),d(d){};
};
inline bool istar(int x,int y){return tag[x][y]>;}
inline bool isok(int x,int y){ return (x>&&x<=n)&&(y>&&y<=m)&&g[x][y]!='D';}
inline int cmp(node a,node b){ return g[a.x][a.y]<g[b.x][b.y];}
bool binary(int cap)
{
memset(dp,-,sizeof(dp));
dp[][]=cap;
for(int s=; s<(<<n); s++)
{
for(int i=; i<=n; i++)
{
if( (s&(<<i-))== ) continue; //未走
for(int j=; j<=n; j++)
{
if( s&(<<j-) ) continue; //只能走1次
int add= j<=egy?cap:-;
if( dis[i][j]> && dp[s][i]>=dis[i][j] ) //前提要走得到那个位置
dp[s|(<<j-)][j]=max(dp[s|(<<j-)][j], max(dp[s][i]-dis[i][j],add));
}
}
}
int mod=(<<n)-(<<egy)+, ans=-INF;
for(int s=; s<(<<n); s++)
{
if( (s&mod)==mod )
{
for(int i=; i<=n; i++)
ans=max(ans, dp[s][i]);
}
}
return ans>=;
} deque<node> que;
void BFS(int x,int y) //求最短路
{
memset(vis,,sizeof(vis));
que.clear();
que.push_back(node(x,y,));
vis[x][y]=true;
while(!que.empty())
{
node t=que.front();que.pop_front();
if( istar(t.x,t.y) ) //记录最短路
dis[tag[x][y]][tag[t.x][t.y]]=t.d;
if(isok(t.x-,t.y)&&!vis[t.x-][t.y])
{
que.push_back(node(t.x-,t.y,t.d+) );
vis[t.x-][t.y]=true;
}
if(isok(t.x+,t.y)&&!vis[t.x+][t.y])
{
que.push_back(node(t.x+,t.y,t.d+) );
vis[t.x+][t.y]=true;
}
if(isok(t.x,t.y-)&&!vis[t.x][t.y-])
{
que.push_back(node(t.x,t.y-,t.d+) );
vis[t.x][t.y-]=true;
}
if(isok(t.x,t.y+)&&!vis[t.x][t.y+])
{
que.push_back(node(t.x,t.y+,t.d+) );
vis[t.x][t.y+]=true;
}
}
} int cal()
{
vector<node> vect; //关键点
for(int i=; i<=n; i++) //编号
for(int j=; j<=m; j++)
if(g[i][j]!='S'&&g[i][j]!='D')
vect.push_back(node(i,j,)); sort(vect.begin(), vect.end(), cmp); //按字典序排序
for(int i=; i<vect.size(); i++) //编号
tag[vect[i].x][vect[i].y]=i+; egy=;
for(int i=; i<vect.size(); i++)
{
if(g[vect[i].x][vect[i].y]=='G') egy++;
BFS(vect[i].x,vect[i].y); //计算最短路
}
n=vect.size();
if(egy==n) return ; //无开关？
if(!binary()) return -; //不可达 int L=, R=;
while(L<R) //二分答案
{
int mid=R-(R-L+)/;
if( binary(mid) ) R=mid;
else L=mid+;
}
return R;
} int main()
{
//freopen("input.txt","r",stdin);
while(scanf("%d%d",&n,&m), n+m)
{
memset(tag,,sizeof(tag));
memset(dis,-,sizeof(dis)); for(int i=; i<=n; i++) scanf("%s",g[i]+);
printf("%d\n",cal());
}
return ;
}
AC代码