題意是已知一幅矩陣迷宮，給起點，開始時充滿電，要求是遍歷給定的點，每移動一次花費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]!='D') addedge(i*m+j,i*m+j+1); } /*for(i=0;i<ids;i++){ for(j=0;j<ids;j++) printf("%d ",dis[i][j]); puts(""); } puts("");*/ for(i=0;i<ids;i++) bfs(c[i][0]*m+c[i][1]); int l=0,r=n*m*(ids-1),mid,ans=-1; while(l<=r){ int mid=(l+r)>>1; if(solve(mid)){ ans=mid; r=mid-1; } else l=mid+1; } printf("%d\n",ans); } return 0; } DFS做法（用時31ms） [cpp] #include <cstdio> #include <cstring> #include <queue> using namespace std; struct Edge{ int v,next; }edge[2000]; int head[300],cnt,ids,fin,mid; 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 has[20]; int dfs(int pos,int len,int sta){ if((sta&fin)==fin)return 1; for(int i=0;i<ids;i++){ if(has[i] || dis[pos][i]==-1)continue; if(len>=dis[pos][i]){ if(map[c[i][0]][c[i][1]]=='G'){ has[i]=1; if(dfs(i,mid,sta|(1<<i)))return 1; has[i]=0; } else{ has[i]=1; if(dfs(i,len-dis[pos][i],sta|(1<<i)))return 1; has[i]=0; } } } 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]!='D') addedge(i*m+j,i*m+j+1); } for(i=0;i<ids;i++) bfs(c[i][0]*m+c[i][1]); int flag=1; for(i=1;i<ids;i++){ if(map[c[i][0]][c[i][1]]=='Y') if(dis[0][i]==-1){ flag=0; break; } } int ans=-1; if(flag){ int l=0,r=n*m*(ids-1); while(l<=r){ mid=(l+r)>>1; memset(has,0,sizeof(has)); has[0]=1; www.2cto.com if(dfs(0,mid,1)){ ans=mid; r=mid-1; } else l=mid+1; } } printf("%d\n",ans); } return 0; }
