解題思路：這道題屬于圖上來回走的問題，可以把重復走的過程弱化，即只強調從u->v的結果，中間經過的節點都不考慮。這道題里面'G','F','Y'是重要的節點，其余的點我們是可以忽略的，也就是說，假設從u->v，我們只需要知道最短路徑是多少就可以了，至于是怎么走的，中間繞過了多少個'D'都不是我們關心的。這樣我們就只需要用bfs找到'G','F','Y'兩兩之間的最短路徑，剩下的就是一個典型的TSP問題了。對于最小的電池量，可以二分答案，這里很容易想到。在dfs中，我們同樣只要知道兩點之間的最短路徑就可以了，并不需要知道如何走過來的，此外，由于每個'Y'都必須要走到，且數據量較小，所以可以用狀態壓縮。

對于這種圖上來回走的問題，可以把重復走的過程弱化，只強調走的結果。

#include<iostream> #include<cstring> #include<queue> #include<algorithm>using namespace std;struct edge {int to,next; }e[2000];struct node {int vid,step; };char mp[20][20]; int id[20][20],c[20][2],head[300],dis[20][20]; int cnt,obj,ids,mid,m,n; bool mk[20];void init() {memset(id,-1,sizeof(id));memset(dis,-1,sizeof(dis));memset(head,-1,sizeof(head));cnt=0;ids=1;obj=0; }void add(int x,int y) {e[cnt].to=y;e[cnt].next=head[x];head[x]=cnt++; }void bfs(int x) {int u,v;node djw,cur,next;queue<node> q;bool vis[400];memset(vis,0,sizeof(vis));djw.vid=x;djw.step=0;q.push(djw);vis[x]=true;while(!q.empty()){cur=q.front();q.pop();u=cur.vid;if(id[u/m][u%m]!=-1)dis[id[x/m][x%m]][id[u/m][u%m]]=cur.step;for(int i=head[u];i!=-1;i=e[i].next){v=e[i].to;if(!vis[v]){vis[v]=true;next.vid=v;next.step=cur.step+1;q.push(next);}}} }int dfs(int bag,int pos,int sta) {if((sta&obj)==obj) return 1;for(int i=0;i<ids;i++){if(mk[i] || dis[pos][i]==-1) continue;if(dis[pos][i]<=bag){if(mp[c[i][0]][c[i][1]]=='G'){mk[i]=true;if(dfs(mid,i,sta|(1<<i))) return 1;mk[i]=false;}else{mk[i]=true;if(dfs(bag-dis[pos][i],i,sta|(1<<i))) return 1;mk[i]=false;}}}return 0; }int main() {while(scanf("%d%d",&n,&m)!=EOF){if(n==0 && m==0)break;init();for(int i=0;i<n;i++)scanf("%s",mp[i]);for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(mp[i][j]=='D') continue;if(mp[i][j]=='F'){c[0][0]=i;c[0][1]=j;id[i][j]=0;}else if(mp[i][j]=='G'){c[ids][0]=i;c[ids][1]=j;id[i][j]=ids++;}else if(mp[i][j]=='Y'){c[ids][0]=i;c[ids][1]=j;obj|=(1<<ids);id[i][j]=ids++;}if(i-1>=0 && mp[i-1][j]!='D')add(i*m+j,(i-1)*m+j);if(i+1<n && mp[i+1][j]!='D')add(i*m+j,(i+1)*m+j);if(j-1>=0 && mp[i][j-1]!='D')add(i*m+j,i*m+j-1);if(j+1<m && mp[i][j+1]!='D')add(i*m+j,i*m+j+1);}}for(int i=0;i<ids;i++)bfs(c[i][0]*m+c[i][1]);int flag=1;for(int i=1;i<ids;i++){if(mp[c[i][0]][c[i][1]]=='Y' && 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(mk,0,sizeof(mk));mk[0]=true;if(dfs(mid,0,1)){ans=mid;r=mid-1;}elsel=mid+1;}}printf("%d\n",ans);}return 0; }

總結

以上是生活随笔為你收集整理的hdu 3681(bfs+dfs+状态压缩)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。