当前位置:编程学习 > C/C++ >>

HDU 3681 Prison Break 哈密顿回路DP

题意是已知一幅矩阵迷宫,給起点,开始时充满电,要求是遍历给定的点,每移动一次花费1,迷宫中有若干充电池可充满电(每个充电池只能用一次),求原始电量最少是多少*/
 
首先抽象出起点、终点、充电池,建立他们的最短路径图,二分枚举原始电量 从而转化为 哈密尔顿回路的状态DP问题 。这样建图原理是:对于原图当前用不用充电池 在新图中 我们可以用两种不同的边来表示(在新图中通过一条边移动到一个充电池则一定用此充电池,而在边上经过充电池时不用)
 
BFS做法(用时421ms)
 
[cpp]  
#include <cstdio>  
#include <cstring>  
#include <queue>  
using namespace std;  
  
struct Edge{  
    int v,next;  
}edge[2000];  
int head[300],cnt,ids,fin;  
  
int n,m;  
char map[20][20];  
int id[20][20];  
int c[20][2];  
int dis[20][20];  
  
struct Node{  
    int s,d;  
};  
  
void init(){  
    memset(head,-1,sizeof(head));  
    memset(id,-1,sizeof(id));  
    memset(dis,-1,sizeof(dis));  
    cnt=0,ids=1,fin=0;  
}  
void addedge(int u,int v){  
    edge[cnt].v=v;  
    edge[cnt].next=head[u];  
    head[u]=cnt++;  
}  
  
void bfs(int s){  
    int i,j,u,v;  
    struct Node tem,tem1;  
    queue<struct Node>q;  
    bool ok[400];  
    memset(ok,0,sizeof(ok));  
    tem.s=s,tem.d=0;  
    q.push(tem);  
    ok[s]=1;  
    while(!q.empty()){  
        tem=q.front();  
        q.pop();  
        u=tem.s;  
        if(id[u/m][u%m]!=-1) dis[id[s/m][s%m]][id[u/m][u%m]]=tem.d;  
        for(i=head[u];i!=-1;i=edge[i].next){  
            v=edge[i].v;  
            if(ok[v])continue;  
            ok[v]=1;  
            tem1.s=v;  
            tem1.d=tem.d+1;  
            q.push(tem1);  
        }  
    }  
}  
int dp[1<<16][16];  
bool solve(int mid){  
    int i,j,k;  
    memset(dp,-1,sizeof(dp));  
    dp[1][0]=mid;  
    for(i=0;i<(1<<ids);i++)  
        for(j=0;j<ids;j++){  
            if((i&(1<<j)==0) || dp[i][j]==-1)continue;  
            if((i&fin)==fin)  
                return 1;  
            for(k=0;k<ids;k++){  
                if(i&(1<<k))continue;  
                if(dis[k][j]==-1)continue;  
                if(dp[i][j]>=dis[k][j]){  
                    if(dp[i|(1<<k)][k]==-1 || dp[i|(1<<k)][k]<dp[i][j]-dis[k][j])  
                        dp[i|(1<<k)][k]=dp[i][j]-dis[k][j];  
                    if(map[c[k][0]][c[k][1]]=='G')  
                        dp[i|(1<<k)][k]=mid;  
                }  
            }  
        }  
    return 0;  
}  
int main(){  
    int i,j,k;  
    while(scanf("%d %d",&n,&m) && n!=0 && m!=0){  
        init();  
        for(i=0;i<n;i++)  
            scanf("%s",map[i]);  
        for(i=0;i<n;i++)  
            for(j=0;j<m;j++){  
                if(map[i][j]=='D')continue;  
                if(map[i][j]=='F'){  
                    c[0][0]=i;  
                    c[0][1]=j;  
                    id[i][j]=0;  
                }  
                else if(map[i][j]=='G'){  
                    c[ids][0]=i;  
                    c[ids][1]=j;  
                    id[i][j]=ids++;  
                }  
                else if(map[i][j]=='Y'){  
                    c[ids][0]=i;  
                    c[ids][1]=j;  
                    id[i][j]=ids++;  
                    fin|=(1<<(ids-1));  
                }  
                if(i-1>=0 && map[i-1][j]!='D')  
                    addedge(i*m+j,(i-1)*m+j);  
                if(i+1<n && map[i+1][j]!='D')  
                    addedge(i*m+j,(i+1)*m+j);  
                if(j-1>=0 && map[i][j-1]!='D')  
                    addedge(i*m+j,i*m+j-1);  
                if(j+1<m && map[i][j+1]!='
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,