HDU 3502 BFS+状压DP

给出N*M矩阵

x-1：不可走

x=0：可走

x>0:：可走，且获得X能量

从（0，0）点走到（n-1，m-1）点，每走一步需要花费一点能量，问能走到出口的最大剩余能量

hint：

特判起点是否有能量，如果没有直接 loss

走到终点是可以选择先不出去，而去拿其他能量

BFS出每个点包括终点的最短路，然后状压DP即可

#include "stdio.h"
#include "string.h"
#include "queue"
using namespace std;

const int dir[4][2]={ {1,0},{-1,0},{0,1},{0,-1} };
const int inf=0x3f3f3f3f;
struct Mark
{
    int x,y,v;
}mark[20];

struct node
{
    int x,y,t;
};
int dis[20][20],str[270][270],used[270][270],id[270][270];
int b[20],dp[300010][20];
int n,m,cnt;

int Max(int a,int b)
{
    if (a<b) return b;
    else return a;
}

int Min(int a,int b)
{
    if (a<b) return a;
    else return b;
}

void BFS(int w)
{
    queue<node>q;
    node cur,next;
    int i;
    cur.x=mark[w].x;
    cur.y=mark[w].y;
    cur.t=0;
    memset(used,0,sizeof(used));
    used[mark[w].x][mark[w].y]=1;
    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.y<0 || next.x>=n || next.y>=m) continue;
            if (str[next.x][next.y]==-1) continue;
            if (used[next.x][next.y]==0)
            {
                used[next.x][next.y]=1;
                next.t=cur.t+1;
                dis[id[next.x][next.y]][w]=dis[w][id[next.x][next.y]]=Min(dis[w][id[next.x][next.y]],next.t);
                q.push(next);
            }
        }
    }
}

int main()
{
    int i,j,mm,l,ans;
    b[0]=1;
    for (i=1;i<=18;i++)
        b[i]=b[i-1]*2;
    while (scanf("%d%d",&n,&m)!=EOF)
    {
        for (i=0;i<n;i++)
            for (j=0;j<m;j++)
            scanf("%d",&str[i][j]);
        if (str[0][0]==0 && n+m!=2)
        {
            printf("you loss!\n");
            continue;
        }
        if (n+m==2)
        {
            printf("%d\n",str[0][0]);
            continue;
        }

        cnt=0;
        memset(id,-1,sizeof(id));
        for (i=0;i<n;i++)
            for (j=0;j<m;j++)
            if (str[i][j]>0)
            {
                id[i][j]=cnt;
                mark[cnt].x=i;
                mark[cnt].y=j;
                mark[cnt++].v=str[i][j];
            }
        if (str[n-1][m-1]==0)
        {
            mark[cnt].x=n-1;
            mark[cnt].y=m-1;
            id[n-1][m-1]=cnt;
            mark[cnt++].v=0;
        }
        memset(dis,inf,sizeof(dis));
        for (i=0;i<cnt;i++)
            dis[i][i]=0;
        for (i=0;i<cnt-1;i++)
            BFS(i);
        memset(dp,-1,sizeof(dp));
        dp[1][0]=mark[0].v;
        mm=b[cnt]-1;
        ans=-1;
        for (l=1;l<mm;l++)
            for (i=0;i<cnt;i++)
            if ((b[i]&l)!=0)
                for (j=0;j<cnt;j++)
                if ((b[j]&l)==0)
                {
                    if (dis[i][j]>dp[l][i]) continue;
                    if (dp[l+b[j]][j]==-1) dp[l+b[j]][j]=dp[l][i]-dis[i][j]+str[mark[j].x][mark[j].y];
                    else dp[l+b[j]][j]=Max(dp[l+b[j]][j],dp[l][i]-dis[i][j]+str[mark[j].x][mark[j].y]);

                    ans=Max(ans,dp[l+b[j]][j]-dis[j][cnt-1]);
                }

        if (ans==-1) printf("you loss!\n");
        else printf("%d\n",ans);
    }
    return 0;
}

HDU 3502 BFS+状压DP

原文：http://blog.csdn.net/u011932355/article/details/44679277