題目鏈接：點擊查看

題目大意：孫悟空要走迷宮去救唐僧，給出n和m約束迷宮大小：

迷宮中：

S代表起點

T代表終點

B代表氧氣區，經過可以獲得一罐氧氣，最多儲存5罐氧氣

#代表毒氣區，經過需要花費2個時間單位，并且消耗一罐氧氣

P表示加速區，經過可以減少一個時間單位

.表示正常路段

題目分析：寫過買鹽的那個題之后，寫這種題就很順手了，這個題需要開一個三維的數組維護狀態，其中兩維用來描述坐標中的x和y，剩下一維用來描述身上的氧氣管數量，即dp[x][y][b]，可以用dp+bfs+普通隊列跑一邊整個過程，也可以用優先隊列維護時間，兩個做法的時間復雜度在這個題目中差距并不大，所以都是可以的：

優先隊列+bfs：

#include<iostream> #include<cstdio> #include<vector> #include<cstring> #include<algorithm> #include<queue> #include<set> #include<string> using namespace std; typedef long long LL;const int inf=0x3f3f3f3f;const int N=110;int n,m;const int b[4][2]={0,1,0,-1,1,0,-1,0};struct Node {int x,y,time,b;Node(int X,int Y,int B,int TIME){x=X;y=Y;b=B;time=TIME;}bool operator<(const Node& a)const{return time>a.time;} };char maze[N][N];bool vis[N][N][10];//vis[x][y][b]int bfs(int x,int y) {int ans=-1;memset(vis,0,sizeof(vis));vis[x][y][0]=true;priority_queue<Node>q;q.push(Node(x,y,0,0));while(!q.empty()){Node temp=q.top();q.pop();for(int k=0;k<4;k++){int xx=temp.x+b[k][0];int yy=temp.y+b[k][1];int b=temp.b;int time=temp.time+1;if(xx<0||yy<0||xx>=n||yy>=m)continue;if(maze[xx][yy]=='#'&&b==0)continue;if(maze[xx][yy]=='#'){b--;time++;}else if(maze[xx][yy]=='B'&&b<5){b++;}else if(maze[xx][yy]=='P'){time--;}if(maze[xx][yy]=='T')return time;if(vis[xx][yy][b])continue;vis[xx][yy][b]=true;q.push(Node(xx,yy,b,time));}}return -1; }int main() { nmsl:while(scanf("%d%d",&n,&m)!=EOF&&n+m){for(int i=0;i<n;i++)scanf("%s",maze[i]);for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(maze[i][j]=='S'){printf("%d\n",bfs(i,j));goto nmsl;}}return 0; }

普通隊列+bfs+dp：

#include<iostream> #include<cstdio> #include<vector> #include<cstring> #include<algorithm> #include<queue> #include<set> #include<string> using namespace std; typedef long long LL;const int inf=0x3f3f3f3f;const int N=110;int n,m;const int b[4][2]={0,1,0,-1,1,0,-1,0};struct Node {int x,y,b;Node(int X,int Y,int B){x=X;y=Y;b=B;} };char maze[N][N];int dp[N][N][10];//dp[x][y][b]int bfs(int x,int y) {memset(dp,inf,sizeof(dp));dp[x][y][0]=0;queue<Node>q;q.push(Node(x,y,0));while(!q.empty()){Node temp=q.front();q.pop();for(int k=0;k<4;k++){int xx=temp.x+b[k][0];int yy=temp.y+b[k][1];int b=temp.b;int time=dp[temp.x][temp.y][b]+1;if(xx<0||yy<0||xx>=n||yy>=m)continue;if(maze[xx][yy]=='#'&&b==0)continue;if(maze[xx][yy]=='#'){b--;time++;}else if(maze[xx][yy]=='B'&&b<5){b++;}else if(maze[xx][yy]=='P'){time--;}if(dp[xx][yy][b]<=time)//注意這里需要轉移狀態，因為首先到達該狀態的并不一定是最優解continue;dp[xx][yy][b]=time;q.push(Node(xx,yy,b));}}int ans=inf;for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(maze[i][j]=='T')for(int k=0;k<=5;k++) if(dp[i][j][k]!=-1)ans=min(ans,dp[i][j][k]);if(ans==inf)return -1;return ans; }int main() { nmsl:while(scanf("%d%d",&n,&m)!=EOF&&n+m){for(int i=0;i<n;i++)scanf("%s",maze[i]);for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(maze[i][j]=='S'){printf("%d\n",bfs(i,j));goto nmsl;}}return 0; }

?

總結

以上是生活随笔為你收集整理的HihoCoder - 1828 Saving Tang Monk II(bfs+动态规划/bfs+优先队列)的全部內容，希望文章能夠幫你解決所遇到的問題。

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