题意:走迷宫,有传送阵,移动花费1秒,传送花费3秒,求到达终点的最短时间。
思路:最短路问题,首先想到的是Dijkstra算法,但是题目数据不大,建图起来麻烦(其实不会),所以我们直接用bfs跑一便就行了,一个多了几个传送阵的迷宫问题,丢进优先队列里搜索时特判一下就行了,一些细节的说明在代码上有注释说明了。
代码:
#include<stdio.h> #include<algorithm> #include<string.h> #include<math.h> #include<queue> using namespace std; typedef long long ll; int n,m,q,i,j,sx,sy,ex,ey; char a[305][305];//地图 int xx[]={1,-1,0,0},yy[]={0,0,1,-1};//方向数组 int vis[305][305];//1为可访问,0为不可访问 struct Hi{ int x,y,step; bool operator<(const Hi & ano) const {//重写堆方法 return step > ano.step; } }; Hi convey[305][305];//传送门 priority_queue<Hi>que; void bfs(){ while(!que.empty()){ que.pop();//注意清空队列 } vis[sx][sy]=0; que.push((Hi){sx,sy,0}); while(!que.empty()){ int nowx=que.top().x; int nowy=que.top().y; int nowt=que.top().step; if(nowx==ex && nowy==ey){//找到直接return printf("%d\n",nowt); return; } que.pop(); if(convey[nowx][nowy].step==1 && vis[convey[nowx][nowy].x][convey[nowx][nowy].y]){//判断当前点是否为有效传送点 que.emplace((Hi){convey[nowx][nowy].x,convey[nowx][nowy].y,nowt+3}); } for(i=0;i<4;i++){ int dx=xx[i]+nowx; int dy=yy[i]+nowy; if(a[dx][dy]!='#' && vis[dx][dy]!=0){//可行路 que.emplace((Hi){dx,dy,nowt+1}); vis[dx][dy]=0;//这里说明一下:如果新的点是通过上下左右一步直接走到的,可以标记掉,因为是附近的。 //可如果是传送门过去的就不要标记了,因为传送门过去的不一定最优,可能还是远路呢。 } } } printf("-1\n"); } int main() { while(scanf("%d%d%d",&n,&m,&q)!=EOF){ memset(a,'\0',sizeof(a)); memset(convey,0,sizeof(convey)); memset(vis,0,sizeof(vis)); for(i=0;i<n;i++){ scanf("%s",a[i]); for(j=0;j<m;j++){ if(a[i][j]=='S'){ sx=i; sy=j; } else if(a[i][j]=='T'){ ex=i; ey=j; } vis[i][j]=1;//地图可行区域为1 } } while(q--){ int x1,x2,y1,y2; scanf("%d%d%d%d",&x1,&y1,&x2,&y2); convey[x1][y1].x=x2; convey[x1][y1].y=y2; if(a[x2][y2] != '#')//传送终点没有陷阱 convey[x1][y1].step=1;//step在该数组中1表示可行,0表示不可行 } bfs(); } }