题意：一幅矩阵迷宫，給起点，开始时充满电，要求是遍历给定的点，每移动一次花费1，
迷宫中有若干充电池可充满电（每个充电池只能用一次），求原始电量最少是多少。
分析：
1、由于所有‘Y‘处一定要走到，‘G‘可以走也可以不走，且他们的总个数最多只有15个。
the sum of energy pools and power switches is less than 15.
因此可以用状态压缩思想记录最终的状态。
因此要给这些符号所在的位置编号。 用hash思想把图中各符号的位置用横纵坐标唯一表示。
即posid=x*列数+y。
2、重新建图，把能走的点之间建边，然后bfs出图中任意两个点之间的最短距离。
3、二分枚举原始电量，找到最小值。
验证能否达到末态的过程中，如果要走的点为‘G‘，则电量为原始的满电量，否则为这一步的起点
位置电量 - 起点到终点的最短距离。
bfs+dfs
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
struct edge
{
int to,next;
}e[2000];
struct node
{
int vid,step;
};
char mp[20][20];
int id[20][20],c[20][2],head[300],dis[20][20];
int cnt,obj,ids,mid,m,n;
bool mk[20];
void init()
{
memset(id,-1,sizeof(id));
memset(dis,-1,sizeof(dis));
memset(head,-1,sizeof(head));
cnt=0;ids=1;obj=0;
}
void add(int x,int y)
{
e[cnt].to=y;
e[cnt].next=head[x];
head[x]=cnt++;
}
void bfs(int x)
{
int u,v;
node djw,cur,next;
queue<node> q;
bool vis[400];
memset(vis,0,sizeof(vis));
djw.vid=x;
djw.step=0;
q.push(djw);
vis[x]=true;
while(!q.empty())
{
cur=q.front();
q.pop();
u=cur.vid;
if(id[u/m][u%m]!=-1)
dis[id[x/m][x%m]][id[u/m][u%m]]=cur.step;
for(int i=head[u];i!=-1;i=e[i].next)
{
v=e[i].to;
if(!vis[v])
{
vis[v]=true;
next.vid=v;
next.step=cur.step+1;
q.push(next);
}
}
}
}
int dfs(int bag,int pos,int sta)
{
if((sta&obj)==obj) return 1;
for(int i=0;i<ids;i++)
{
if(mk[i] || dis[pos][i]==-1) continue;
if(dis[pos][i]<=bag)
{
if(mp[c[i][0]][c[i][1]]==‘G‘)
{
mk[i]=true;
if(dfs(mid,i,sta|(1<<i))) return 1;
mk[i]=false;
}
else
{
mk[i]=true;
if(dfs(bag-dis[pos][i],i,sta|(1<<i))) return 1;
mk[i]=false;
}
}
}
return 0;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n==0 && m==0)
break;
init();
for(int i=0;i<n;i++)
scanf("%s",mp[i]);
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(mp[i][j]==‘D‘) continue;
if(mp[i][j]==‘F‘)
{
c[0][0]=i;
c[0][1]=j;
id[i][j]=0;
}
else if(mp[i][j]==‘G‘)
{
c[ids][0]=i;
c[ids][1]=j;
id[i][j]=ids++;
}
else if(mp[i][j]==‘Y‘)
{
c[ids][0]=i;
c[ids][1]=j;
obj|=(1<<ids);
id[i][j]=ids++;
}
if(i-1>=0 && mp[i-1][j]!=‘D‘)
add(i*m+j,(i-1)*m+j);
if(i+1<n && mp[i+1][j]!=‘D‘)
add(i*m+j,(i+1)*m+j);
if(j-1>=0 && mp[i][j-1]!=‘D‘)
add(i*m+j,i*m+j-1);
if(j+1<m && mp[i][j+1]!=‘D‘)
add(i*m+j,i*m+j+1);
}
}
for(int i=0;i<ids;i++)
bfs(c[i][0]*m+c[i][1]);
int flag=1;
for(int i=1;i<ids;i++)
{
if(mp[c[i][0]][c[i][1]]==‘Y‘ && dis[0][i]==-1)
{
flag=0;
break;
}
}
int ans=-1;
if(flag)
{
int l=0,r=n*m*(ids-1);
while(l<=r)
{
mid=(l+r)>>1;
memset(mk,0,sizeof(mk));
mk[0]=true;
if(dfs(mid,0,1))
{
ans=mid;
r=mid-1;
}
else
l=mid+1;
}
}
printf("%d\n",ans);
}
return 0;
}
dp+bfs
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
struct edge
{
int to,next;
}e[2000];
struct node
{
int vid,step;
};
char mp[20][20];
int id[20][20],c[20][2],head[300],dis[20][20];
int dp[1<<16][16];
int cnt,obj,ids,mid,m,n;
void init()
{
memset(id,-1,sizeof(id));
memset(dis,-1,sizeof(dis));
memset(head,-1,sizeof(head));
cnt=0;ids=1;obj=0;
}
void add(int x,int y)
{
e[cnt].to=y;
e[cnt].next=head[x];
head[x]=cnt++;
}
void bfs(int x)
{
int u,v;
node djw,cur,next;
queue<node> q;
bool vis[400];
memset(vis,0,sizeof(vis));
djw.vid=x;
djw.step=0;
q.push(djw);
vis[x]=true;
while(!q.empty())
{
cur=q.front();
q.pop();
u=cur.vid;
if(id[u/m][u%m]!=-1)
dis[id[x/m][x%m]][id[u/m][u%m]]=cur.step;
for(int i=head[u];i!=-1;i=e[i].next)
{
v=e[i].to;
if(!vis[v])
{
vis[v]=true;
next.vid=v;
next.step=cur.step+1;
q.push(next);
}
}
}
}
int solve(int mid)
{
memset(dp,-1,sizeof(dp));
dp[1][0]=mid;
for(int i=0;i<(1<<ids);i++)
{
for(int j=0;j<ids;j++)
{
if((i&(1<<j)==0) || dp[i][j]==-1) continue;
if((i&obj)==obj) return 1;
for(int k=0;k<ids;k++)
{
if(j==k || i&(1<<k)) continue;
if(dis[j][k]==-1) continue;
if(dp[i][j]>=dis[j][k])
{
if(dp[i|(1<<k)][k]==-1 || dp[i|(1<<k)][k]<dp[i][j]-dis[j][k])
dp[i|(1<<k)][k]=dp[i][j]-dis[j][k];
if(mp[c[k][0]][c[k][1]]==‘G‘)
dp[i|(1<<k)][k]=mid;
}
}
}
}
return 0;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n==0 && m==0)
break;
init();
for(int i=0;i<n;i++)
scanf("%s",mp[i]);
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(mp[i][j]==‘D‘) continue;
if(mp[i][j]==‘F‘)
{
c[0][0]=i;
c[0][1]=j;
id[i][j]=0;
}
else if(mp[i][j]==‘G‘)
{
c[ids][0]=i;
c[ids][1]=j;
id[i][j]=ids++;
}
else if(mp[i][j]==‘Y‘)
{
c[ids][0]=i;
c[ids][1]=j;
id[i][j]=ids++;
obj|=(1<<(ids-1));
}
if(i-1>=0 && mp[i-1][j]!=‘D‘)
add(i*m+j,(i-1)*m+j);
if(i+1<n && mp[i+1][j]!=‘D‘)
add(i*m+j,(i+1)*m+j);
if(j-1>=0 && mp[i][j-1]!=‘D‘)
add(i*m+j,i*m+j-1);
if(j+1<m && mp[i][j+1]!=‘D‘)
add(i*m+j,i*m+j+1);
}
}
for(int i=0;i<ids;i++)
bfs(c[i][0]*m+c[i][1]);
int ans=-1;
int l=0,r=n*m*(ids-1);
while(l<=r)
{
mid=(l+r)>>1;
if(solve(mid))
{
ans=mid;
r=mid-1;
}
else
l=mid+1;
}
printf("%d\n",ans);
}
return 0;
}