首页 > ACM题库 > HDU-杭电 > hdu 3681-prison break-动态规划-[解题报告]hoj
2014
11-30

hdu 3681-prison break-动态规划-[解题报告]hoj

Prison Break

Time Limit: 5000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3214    Accepted Submission(s): 829



Problem Description
Rompire is a robot kingdom and a lot of robots live there peacefully. But one day, the king of Rompire was captured by human beings. His thinking circuit was changed by human and thus became a tyrant. All those who are against him were put into jail, including
our clever Micheal#1. Now it’s time to escape, but Micheal#1 needs an optimal plan and he contacts you, one of his human friends, for help.
The jail area is a rectangle contains n×m little grids, each grid might be one of the following: 
1) Empty area, represented by a capital letter ‘S’. 
2) The starting position of Micheal#1, represented by a capital letter ‘F’. 
3) Energy pool, represented by a capital letter ‘G’. When entering an energy pool, Micheal#1 can use it to charge his battery ONLY ONCE. After the charging, Micheal#1’s battery will become FULL and the energy pool will become an empty area. Of course, passing
an energy pool without using it is allowed.
4) Laser sensor, represented by a capital letter ‘D’. Since it is extremely sensitive, Micheal#1 cannot step into a grid with a laser sensor. 
5) Power switch, represented by a capital letter ‘Y’. Once Micheal#1 steps into a grid with a Power switch, he will certainly turn it off. 

In order to escape from the jail, Micheal#1 need to turn off all the power switches to stop the electric web on the roof—then he can just fly away. Moving to an adjacent grid (directly up, down, left or right) will cost 1 unit of energy and only moving operation
costs energy. Of course, Micheal#1 cannot move when his battery contains no energy. 

The larger the battery is, the more energy it can save. But larger battery means more weight and higher probability of being found by the weight sensor. So Micheal#1 needs to make his battery as small as possible, and still large enough to hold all energy he
need. Assuming that the size of the battery equals to maximum units of energy that can be saved in the battery, and Micheal#1 is fully charged at the beginning, Please tell him the minimum size of the battery needed for his Prison break.

 


Input
Input contains multiple test cases, ended by 0 0. For each test case, the first line contains two integer numbers n and m showing the size of the jail. Next n lines consist of m capital letters each, which stands for the description of the jail.You can assume
that 1<=n,m<=15, and the sum of energy pools and power switches is less than 15.
 


Output
For each test case, output one integer in a line, representing the minimum size of the battery Micheal#1 needs. If Micheal#1 can’t escape, output -1.
 


Sample Input
5 5 GDDSS SSSFS SYGYS SGSYS SSYSS 0 0
 


Sample Output
4
 

思路:首先提取出各个特殊点(开关位置、充电池、起始位置),对它们进行标号,然后,求它们之间的最短距离。之后,二分枚举可能的初始能量值,进行DP看能否走到目标状态。

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<queue>
#include<algorithm>
#include<iostream>
using namespace std;
#define N 20
const int inf=10000;
int n1,n2,n,m,f;
char g[N][N];
int x[N],y[N];
int dir[4][2]={0,1,0,-1,-1,0,1,0};
int dis[N][N],dist[N][N];
int dp[1<<15][N];
void inti()  //读入数据,把特殊点标号
{
    n1=0;
    int i,j;
    for(i=0; i<n; i++)
    {
        scanf("%s",g[i]);
        for(j=0; j<m; j++)
        {
            if(g[i][j]=='F')
            {
                f=n1;
                x[n1]=i;
                y[n1++]=j;
            }
            else if(g[i][j]=='Y')
            {
                x[n1]=i;
                y[n1++]=j;
            }
        }
    }
    n2=n1;
    for(i=0; i<n; i++)
        for(j=0; j<m; j++)
            if(g[i][j]=='G')
            {
                x[n2]=i;
                y[n2++]=j;
            }
}
void bfs(int x,int y,int dis[][20]) //求一个特殊点到其他各个点最短路
{
    int i,j,u,v;
    queue<int>q1,q2;
    q1.push(x);
    q2.push(y);
    for(i=0;i<n;i++)
        for(j=0;j<m;j++)
        dis[i][j]=inf;
    dis[x][y]=0;
    while(!q1.empty())
    {
        x=q1.front();
        y=q2.front();
        q1.pop();
        q2.pop();
        for(i=0;i<4;i++)
        {
            u=x+dir[i][0];
            v=y+dir[i][1];
            if(u<0||u>=n||v<0||v>=m||g[u][v]=='D')
                continue;
            if(dis[u][v]>dis[x][y]+1)
            {
                dis[u][v]=dis[x][y]+1;
                q1.push(u);
                q2.push(v);
            }
        }
    }
}
bool findd(int t)
{
    int i,j,k,lim=1<<n2,tmp=(1<<n1)-1;
    for(i=0;i<lim;i++)
        for(j=0;j<n2;j++)
        dp[i][j]=-inf;
    dp[1<<f][f]=t;
    for(i=1<<f;i<lim;i++)
    {
        for(j=0;j<n2;j++)
        {
            if(dp[i][j]<0)
                continue;
            if((i&tmp)==tmp) //不一定要相等,包含目标状态就行
                return true;
            for(k=0;k<n2;k++)
            {
                int p=1<<k;
                if(i&p)
                    continue;
                dp[i|p][k]=max(dp[i|p][k],dp[i][j]-dis[j][k]);
                if(dp[i|p][k]>=0&&k>=n1)
                    dp[i|p][k]=t;
            }
        }
    }
    return false;
}
int main()
{
    int i,j;
    while(scanf("%d%d",&n,&m),n||m)
    {
        inti();
        for(i=0; i<n2; i++)
        {
            bfs(x[i],y[i],dist);
            for(j=0; j<n2; j++)  //记录标号后的点相互之间距离
            {
                dis[i][j]=dist[x[j]][y[j]]; 
            }  //i到j的距离等于i点到各个点的最短路
        }
        
        int l=0,r=300,flag=0;
        while(l<=r)       //二分枚举各个可能的能量值
        {
            int mid=(l+r)/2;
            if(findd(mid))
            {
                flag=1;
                r=mid-1;
            }
            else
                l=mid+1;
        }
        if(!flag)
            l=-1;
        printf("%d\n",l);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。


  1. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  2. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.