HDU 3681 BFS&像缩进DP&二分法

N*M矩阵。从F出发点。走完全部Y点。每个人格开支1电源点，去G点，电池充满，D无法访问。最小的开始问什么时候满负荷可以去完全部Y。Y和G总共高达15一

第一BFS所有的F。Y。G之间的最短距离。

然后一半的首发大。对于每次充电。不喜欢缩进DP推断是否可行

#include "stdio.h"

#include "string.h"

#include "queue"

using namespace std;

int inf=0x3f3f3f3f;

int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};

struct node

{

    int x,y,step;

};

struct Mark

{

    int x,y;

}mark[21];

char map[21][21];

int step[21][21],b[21],dp[70010][21],dis[21][21];

int cnt,aim,start,n,m;

int Min(int a,int b)

{

    if (a<b) return a;else return b;

}

void bfs(int x,int y)

{

    queue<node>q;

    node cur,next;

    int i;

    memset(step,inf,sizeof(step));

    step[x][y]=0;

    cur.x=x;

    cur.y=y;

    cur.step=0;

    q.push(cur);

    while (!q.empty())

    {

        cur=q.front();

        q.pop();

        for (i=0;i<4;i++)

        {

            next.x=cur.x+dir[i][0];

            next.y=cur.y+dir[i][1];

            if (next.x<0 || next.x>=n || next.y<0 || next.y>=m) continue;

            if (map[next.x][next.y]=='D') continue;

            if (step[next.x][next.y]!=inf) continue;

            next.step=cur.step+1;

            step[next.x][next.y]=next.step;

            q.push(next);

        }

    }

}

int DP(int key)

{

    int i,j,k;

    memset(dp,inf,sizeof(dp));

    dp[b[start]][start]=0;

    for (i=0;i<b[cnt];i++)

        for (j=0;j<cnt;j++)

            if ((b[j]&i)==b[j] && dp[i][j]!=inf)

            {

                for (k=0;k<cnt;k++)

                    if (k!=j && (b[k]&i)!=b[k] && dp[i][j]+dis[j][k]<=key)

                    {

                        dp[i+b[k]][k]=Min(dp[i+b[k]][k],dp[i][j]+dis[j][k]);

                        if (map[mark[k].x][mark[k].y]=='G') dp[i+b[k]][k]=0;

                        if (((i+b[k])&aim)==aim) return 1;

                    }

            }

    return 0;

}

int main()

{

    int i,j,l,r,mid,ans;

    b[0]=1;

    for (i=1;i<=16;i++)

        b[i]=b[i-1]*2;

    while (scanf("%d%d",&n,&m)!=EOF)

    {

        if (n==0 && m==0) break;

        cnt=0;

        getchar();

        for (i=0;i<n;i++)

            gets(map[i]);

        aim=0;

        for (i=0;i<n;i++)

            for (j=0;j<m;j++)

                if (map[i][j]=='F' || map[i][j]=='Y' || map[i][j]=='G')

                {

                    if (map[i][j]!='G') aim+=b[cnt];

                    if (map[i][j]=='F') start=cnt;

                    mark[cnt].x=i;

                    mark[cnt].y=j;

                    cnt++;

                }

        memset(dis,inf,sizeof(dis));

        for (i=0;i<cnt;i++) // BFS出，F,Y,G之间的最短距离

        {

            bfs(mark[i].x,mark[i].y);

            for (j=0;j<cnt;j++)

                dis[i][j]=step[mark[j].x][mark[j].y];

        }

        l=0; r=n*m;

        ans=-1;

        while (l<=r) // 二分电量

        {

            mid=(l+r)/2;

            if (DP(mid)==1)

            {

                ans=mid;

                r=mid-1;

            }

            else

                l=mid+1;

        }

        printf("%d\n",ans);

    }

    return 0;

}