hdu 3681 * Break

http://acm.hdu.edu.cn/showproblem.php?pid=3681

题意：一个n*m的矩阵，'F'是起点。机器人从F出发，走到G可以充电，走到Y关掉开关，D不能走进，要求把所有开关关掉，且电量最少，并求出该最小电量。

把F，G，Y的坐标存起来，然后用bfs求出它们每两个点最短距离，然后用dp判断是不是可以满足目的状态。 用二分枚举答案。

 #include <cstdio>
 #include <queue>
 #include <cstring>
 #include <algorithm>
 #define maxn 17
 using namespace std;
 const int inf=<<;

 char g[][];
 int n,m;
 int gg[][];
 bool vis[][];
 int dir[][]={{,},{-,},{,},{,-}};
 int sx,sy;
 int spos;
 int epos;
 int cnt;
 int dis[][];
 int dp[(<<maxn)][maxn];
 struct node
 {
     int x,y;
 }p[],st,st1,st2;

 int bfs(int s,int t)
 {
     queue<node>q;
     memset(vis,false,sizeof(vis));
     for(int i=; i<n; i++)
     {
         for(int j=; j<m; j++)
         {
             dis[i][j]=inf;
         }
     }
     dis[p[s].x][p[s].y]=;
     st.x=p[s].x;
     st.y=p[s].y;
     vis[p[s].x][p[s].y]=true;
     q.push(st);
     while(!q.empty())
     {
         st1=q.front();
         q.pop();
         if(st1.x==p[t].x&&st1.y==p[t].y)
         {
             return dis[st1.x][st1.y];
         }
         for(int i=; i<; i++)
         {
             int xx=st1.x+dir[i][];
             int yy=st1.y+dir[i][];
             if(xx>=&&xx<n&&yy>=&&yy<m&&!vis[xx][yy]&&g[xx][yy]!='D')
             {
                 dis[xx][yy]=dis[st1.x][st1.y]+;
                 st2.x=xx;
                 st2.y=yy;
                 vis[xx][yy]=true;
                 q.push(st2);
             }
         }
     }
     return -;
 }

 int ok(int c)
 {
     memset(dp,-,sizeof(dp));
     dp[<<spos][spos]=c;
     for(int i=; i<(<<cnt); i++)
     {
         for(int j=; j<cnt; j++)
         {
             if((i&(<<j))==) continue;
             if(dp[i][j]==-) continue;
             if((i&epos)==epos) return true;
             for(int k=; k<cnt; k++)
             {
                 if(i&(<<k)) continue;
                 if(gg[j][k]==-) continue;
                 if(dp[i][j]<gg[j][k]) continue;
                 if(dp[i|(<<k)][k]==-) dp[i|(<<k)][k]=dp[i][j]-gg[j][k];
                 else dp[i|(<<k)][k]=max(dp[i|(<<k)][k],dp[i][j]-gg[j][k]);
                 int x1=p[k].x,y1=p[k].y;
                 if(g[x1][y1]=='G') dp[i|(<<k)][k]=c;
             }
         }
     }
     return false;
 }

 int main()
 {
     while(scanf("%d%d",&n,&m)!=EOF)
     {
         if(n==&&m==) break;
         cnt=;
         epos=;
         for(int i=; i<n; i++)
         {
             scanf("%s",g[i]);
             for(int j=; j<m; j++)
             {
                 if(g[i][j]=='F')
                 {
                     sx=i; sy=j;
                     spos=cnt;
                     epos|=(<<cnt);
                     p[cnt].x=i;
                     p[cnt++].y=j;
                 }
                 if(g[i][j]=='G')
                 {
                     p[cnt].x=i;
                     p[cnt++].y=j;
                 }
                 if(g[i][j]=='Y')
                 {
                     epos|=(<<cnt);
                     p[cnt].x=i;
                     p[cnt++].y=j;
                 }
             }
         }
         for(int i=; i<cnt; i++)
         {
             for(int j=; j<cnt; j++)
             {
                 if(i==j) gg[i][j]=;
                 else gg[i][j]=bfs(i,j);
             }
         }
         int l=,r=n*m;
         int mid;
         int ans=-;
         while(l<=r)
         {
             mid=(l+r)>>;
             if(ok(mid))
             {
                 ans=mid;
                 r=mid-;
             }
             else l=mid+;
         }
         printf("%d\n",ans);
     }
     return ;
 }