hdu 3681 Prison 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 ;

 }

巴特西

hdu 3681 Prison Break

最新文章

热门文章