思路
：这道题需要用到优先队列，不然过不了，详细思路见注释哦，我写得还是比较详细，肯定能懂哒，注意所开数组范围，不然会wa。有错请指教
#include<bits/stdc++.h>
using namespace std;
const int N = 303;
char mp[N][N];//迷宫
int visit[N][N];//判断是否走过，1走过，0未走
int Qsx[1001];//第i传送门起点x坐标，注意范围，开小了会wa
int Qsy[1001];//传送门y起点坐标
int Qex[1001];//第ig个传送门x终点
int Qey[1001];
int mark[1001][1001];
int n,m;//迷宫：n行，m列
int q;//传送门个数
//左下右上四个方位
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
struct Time
{
int x;
int y;
int time;
friend bool operator<(const Time &a,const Time &b)//定义优先级
{
return a.time >b.time;
}
};
int bfs(int sx,int sy)
{
priority_queue<Time>qu;//结构型优先队列
if(mp[sx][sy]=='#') return -1;//起点为陷阱
qu.push(Time{sx,sy,0});//最初，小明在sx,sy处，所用时间为0
while(!qu.empty())
{
Time s = qu.top();
qu.pop();//出队
if(mp[s.x][s.y]=='T')
{
return s.time;//如果到达终点则返回所用时间
}
Time next;//下一个位置
//要么走传送门，走传送门要注意 终点是否为陷阱
//接下来有两种选择，要么上下左右走
if(mark[s.x][s.y]!=0&&mp[s.x][s.y]!='#')//这个点有传送门而且入口不是陷阱 ，你看我就说用到了吧，
//嘻嘻
{
int i = mark[s.x][s.y] ;
if(mp[Qex[i]][Qey[i]]!='#')//传送门终点不是陷阱 ，而且终点没走过
{
qu.push(Time{Qex[i],Qey[i],s.time+3});
}
}
for(int i=0;i<4;i++)
{
//上第二种，下左右走
next.x = s.x + dx[i];
next.y = s.y + dy[i];
next.time = s.time + 1;
//首先判断是否越界 或者是否是陷阱
if(next.x<0||next.x>n||next.y<0||next.y>m||mp[next.x ][next.y]=='#') continue;
//再判断是否走过
if(visit[next.x][next.y ]==1) continue;
visit[next.x][next.y] = 1;
// cout<<"普通情况 "<<next.time<<endl;
//cout<<next.x<<" "<<next.y<<endl;
qu.push(next);
}
// cout<<"a"<<endl;
}
return -1;//无法走到终点
}
int main()
{
while(cin>>n>>m>>q) //多组出入
{
int sx,sy;//起点
int ex,ey;//终点
//输入迷宫
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
cin>>mp[i][j];
if(mp[i][j]=='S')
{
sx = i;
sy = j;//记录起点坐标
}
}
}
//输入传送门位置
int qsx,qsy;//传送门 起点坐标
int qex,qey;//传送门终点坐标
memset(visit,0,sizeof(visit));//利用memset函数，全部标记为0，表示为走过
memset(mark,0,sizeof(mark));
for(int i=1;i<=q;i++)//输入传送门
{
cin>>Qsx[i]>>Qsy[i]>>Qex[i]>>Qey[i];
mark[Qsx[i]][Qsy[i]] = i;//这传送门的起点标记为第i个，在bfs操作了会用到这个
}
visit[sx][sy] = 1;//起点当然走过啦
int ans = bfs(sx,sy);//调用函数，进行bfs操作
cout<<ans<<endl;
}
return 0;
}
京公网安备 11010502036488号