hdu 3681(bfs+dfs+状态压缩)

解题思路：这道题属于图上来回走的问题，可以把重复走的过程弱化，即只强调从u->v的结果，中间经过的节点都不考虑。这道题里面'G','F','Y'是重要的节点，其余的点我们是可以忽略的，也就是说，假设从u->v，我们只需要知道最短路径是多少就可以了，至于是怎么走的，中间绕过了多少个'D'都不是我们关心的。这样我们就只需要用bfs找到'G','F','Y'两两之间的最短路径，剩下的就是一个典型的TSP问题了。对于最小的电池量，可以二分答案，这里很容易想到。在dfs中，我们同样只要知道两点之间的最短路径就可以了，并不需要知道如何走过来的，此外，由于每个'Y'都必须要走到，且数据量较小，所以可以用状态压缩。

对于这种图上来回走的问题，可以把重复走的过程弱化，只强调走的结果。

#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;
}