一道状态压缩好题

题目大意：

　　就是开局有一个起始点和一些必须经过的点，然后从起始点出发，必须要经过所有的必经点，在此基础上求出最小花费，其中引入一个充电池的概念，即到达这个点后花费会清零，但是每个充电点只能经过一次。输出最小花费，不能到达，输出-1。

题目分析：　　

　　乍一看没有什么思路（搜索就算了，我不知道A*能不能过）。仔细分析，发现搜索显然过不了，观察数据，考虑状态压缩dp。

　　但是发现直接dp好像不是很好设计状态，考虑其他方式+状态压缩dp。

　性质：发现不论怎么走，答案都是有界且单调的，更小的值只会更好。由此，可以考虑二分答案和check

　那么该怎么check呢，那么考虑直接用dp来验证，由于套一个log复杂度不会爆炸，所以可以放心使用

　那么该怎么状态压缩呢？

　考虑到空白格子和棋盘和障碍没有实际的意义，也没有用处，反而会扩大范围导致dp范围存疑，由此考虑初始化。

　这时就是套路了，可以用一遍bfs预处理出所有两点间的距离，无法到达就把距离修改为-1

（细节在代码里说明）

代码实现：

#include<bits/stdc++.h>

using namespace std;
struct pos
{
    int x,y;
    pos(int x=0,int y=0):x(x),y(y) {}//结构体存坐标
};
struct node
{
    int x,y,s;
    node(int x=0,int y=0,int s=0):x(x),y(y),s(s) {}//重新建图
};
vector<pos>a;//邻接表
int n,m,fid,ac;//ac代表目标状态，fid代表起始点在哪一位
int dir[4][2]= {{0,-1},{-1,0},{0,1},{1,0}};//增量数组，在bfs中使用
char Map[20][20];//存原图
int vis[20][20],d[20][20];//vis和d数组
int dp[(1<<15)+10][16];
void input()
{
    a.clear();
    ac=0;
    for(int i=0; i<n; i++)
    {
        scanf("%s",Map[i]);
        for(int j=0; j<m; j++)
        {
            if(Map[i][j]=='F')
            {
                fid=a.size();//记录起始点在哪一位
                ac+=1<<a.size();//修改目标状态，起始点应该被经过
                a.push_back(pos(i,j));
            }
            if(Map[i][j]=='Y')
            {
                ac+=1<<a.size();//修改状态，y应该被经过
                a.push_back(pos(i,j));
            }
            if(Map[i][j]=='G') a.push_back(pos(i,j));//充电池只要存在就可以使用
        }
    }
}
bool ok(int x,int y)
{
    if(0<=x&&x<n&&0<=y&&y<m&&Map[x][y]!='D'&&vis[x][y]==0) return 1;//可行性检验
    return 0;
}
int bfs(pos a,pos b)
{
    node now=node(a.x,a.y,0),next;
    queue<node>q;
    q.push(now);
    memset(vis,0,sizeof(vis));
    vis[a.x][a.y]=1;
    while(q.size())
    {
        now =q.front();
        q.pop();
        if(now.x==b.x&&now.y==b.y) return now.s;
        for(int i=0; i<4; i++)
        {
            next=now;
            next.x+=dir[i][0];
            next.y+=dir[i][1];
            next.s++;
            if(ok(next.x,next.y)) vis[next.x][next.y]=1,q.push(node(next.x,next.y,next.s));
        }
    }
    return -1;
}
void init()
{
　　//预处理距离
    for(int i=0; i<a.size(); i++)
        for(int j=0; j<a.size(); j++)
            d[i][j]=bfs(a[i],a[j]);
}
bool DP(int va)
{
　　//初始化
    memset(dp,-1,sizeof(dp));
　　//目标答案
    dp[1<<fid][fid]=va;
    int len=a.size();//位数
    for(int i=1<<fid;i<1<<len;i++)//枚举当前状态
    {
        for(int j=0;j<len;j++)
        {
            if(dp[i][j]<0) continue;//如果到不了
            if((i&ac)==ac&&dp[i][j]!=-1) return 1;//如果到了目标状态
            for(int k=0;k<len;k++)
            {
                if(i>>k&1) continue;//若当前“想去”的已经走过了
                if(d[j][k]==-1) continue;//如果根本到不了
                int tmp=dp[i][j]-d[j][k];//花费减去
                if(tmp<0) continue;//当前状态已经没有电了，注意，当tmp=0时正好到达，注意条件
                dp[i|(1<<k)][k]=max(dp[i|(1<<k)][k],tmp);//更新答案，因为之前可能已经走过，并且更优
                if(Map[a[k].x][a[k].y]=='G') dp[i|(1<<k)][k]=va;//可以充电，回满电量
            }
        }
    }
    return 0;
}
void solve()
{
    int l=0,r=300,ans=1<<30;//答案初始化正无穷，r<=225
　　//二分答案
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(DP(mid))
        {
            ans=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    if(ans==(1<<30)) ans=-1;
    printf("%d\n",ans);
}
int main()
{
    //freopen("in.txt","r",stdin);
    while(~scanf("%d%d",&n,&m),n+m)
    {
        input();
        init();
        //debug();
        solve();
    }
    return 0;
}