題目鏈接：點擊查看

題目大意：給出一個n*n的正方形網(wǎng)格，其中“.”表示可以走的路，“#”表示障礙物，每次可以向上下左右任意方向走1格，花費1單位時間，再給出m條單向隧道，從隧道的起點進入后可以瞬間從隧道的終點出來，即不花費時間，但是每條隧道只能走一次，現(xiàn)在可以選擇網(wǎng)格中的任何一點作為起點，問在滿足條件并走完全部隧道的情況下的最小時間

題目分析：首先是關于起點選擇的問題，用貪心的思想來考慮，肯定是選擇m條隧道中的某一條隧道的起點作為開始的點才是最優(yōu)選擇，我也不會證明，不過肯定是這樣的！接下來我們可以將這個題目抽象成最短路的模型，因為涉及到了次序問題并且最后每條隧道都需要走一次，所以再抽象成哈密頓路徑的模型，問題就得到解決了

現(xiàn)在的問題是如何抽象成最短路的模型呢，我們通過分析題意可知，需要我們花費時間行走的，只有在某一個隧道的終點到下一個隧道的起點這段路上，所以我們可以用bfs對于兩兩隧道的終點和起點進行路徑的確定，（注意，只能是從某一隧道的終點到下一隧道的起點，因為從某一隧道起點到下一隧道終點是沒有必要的，因為我們完全可以直接從某一隧道的起點穿過該隧道到達該隧道的終點），然后就轉(zhuǎn)換成了最短路的問題，因為已經(jīng)獲得了兩兩隧道之間的距離了，如果無法到達設為inf即可，自己到自己設為0。

然后就是哈密頓路徑的模板了，用dp[i][j]來儲存最短路，i表示當前狀態(tài)為i，j表示最后到達的終點為j，dp[i][j]表示i和j狀態(tài)下的最短路徑，最后說一下初始化吧，初始時dp[(1<<i)][i]=0(0<i<m)，其余初始化為inf，其含義就是某個隧道的起點到達它自己的時間為0。

轉(zhuǎn)移方程直接去代碼中看就好了，注意bfs的寫法，記得判斷x1,y1,x2,y2在一開始就相等的特例，即一條隧道的終點就是另一條隧道的起點，因為忘記這個特例了，WA了將近一個上午。。

上代碼了：

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=(1<<12); int n,m;struct Node {int x,y,step;Node(int X,int Y,int S){x=X;y=Y;step=S;}Node(){} };char maze[20][20];int x1[20],x2[20],y1[20],y2[20];int d[20][20];bool vis[20][20];int dp[(1<<15)+100][20];const int bb[4][2]={1,0,-1,0,0,1,0,-1};int bfs(int a,int b,int c,int d) {queue<Node>q;memset(vis,false,sizeof(vis));vis[a][b]=true;q.push(Node(a,b,0));while(!q.empty()){Node temp=q.front();if(temp.x==c&&temp.y==d)return temp.step;q.pop();for(int i=0;i<4;i++){Node next;next.x=temp.x+bb[i][0];next.y=temp.y+bb[i][1];next.step=temp.step+1;if(next.x<=0||next.x>n||next.y<=0||next.y>n)continue;if(vis[next.x][next.y])continue;if(maze[next.x][next.y]=='#')continue;if(next.x==c&&next.y==d)return next.step;q.push(next);vis[next.x][next.y]=true;}}return inf; }int main() { // freopen("input.txt","r",stdin)while(scanf("%d%d",&n,&m)!=EOF){for(int i=1;i<=n;i++)scanf("%s",maze[i]+1); for(int i=0;i<m;i++)scanf("%d%d%d%d",x1+i,y1+i,x2+i,y2+i);for(int i=0;i<m;i++)for(int j=0;j<m;j++){if(i==j){d[i][j]=0;continue;}d[i][j]=bfs(x2[i],y2[i],x1[j],y1[j]);}int up=(1<<m)-1;for(int i=0;i<=up;i++)for(int j=0;j<m;j++)dp[i][j]=inf;for(int i=0;i<m;i++)dp[(1<<i)][i]=0;for(int i=0;i<=up;i++){for(int j=0;j<m;j++){if(dp[i][j]==inf)continue;if(!((1<<j)&i))continue;for(int k=0;k<m;k++){if(d[j][k]==inf)continue;if(i&(1<<k))continue;dp[i|(1<<k)][k]=min(dp[i|(1<<k)][k],dp[i][j]+d[j][k]);}}}int ans=inf;for(int i=0;i<m;i++)ans=min(ans,dp[up][i]);if(ans==inf)cout<<-1<<endl;elsecout<<ans<<endl;}return 0; }

?

總結

以上是生活随笔為你收集整理的HDU - 4856 Tunnels(哈密顿路径+状压dp)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。