bfs加弹射器

bfs加弹射器

       在与boss的最终决战之后，小蓝来到了冒险的最后一关，在他面前有一个n*m的迷宫，迷宫中道路用’.’表示，墙壁则由‘#’表示。小蓝初始在[1,1]的位置，他只有到达[n,m]才能开启最终的宝藏。小蓝现在迫不及待的想要开启宝藏，所以他想最短的时间内走出迷宫。现在迷宫内有一种特殊的装置 –“弹射器”。弹射器的格子用’*’表示。当走到有弹射器的一格时，小蓝必须选择一个方向，弹射器会让他沿着这个方向弹射 x个距离，不同弹射器的弹射距离可以不同。弹射后的格子如果超过迷宫边界或者是墙壁则不能选择这个方向。小蓝现在可以向上下左右四个方向走，每走一个格子需要消耗一个单位时间，弹射则不消耗时间。求最短需要多少时间小蓝才能走出迷宫。如果无法到达终点，输出-1。

弹射器的数量，位置和弹射距离将在输入中给出。起点和终点一定不是弹射器。

输入描述:
第一行两个整数 n, m，接下来n行，每行m个只包含’.’,’*’,’#’的字符描绘迷宫。

接下来一行一个整数k，下面的k行每行三个整数x, y, w表示在[x,y]格子的弹射器能弹射的距离。（2≤n≤3000,2≤m≤3000, n*m≤500000, 0≤k, w在int范围内）

输出描述:

一行一个整数

输入

3 2
.*
#.
..
1
1 2 2

输出

1

输入

2 2
.*
#.
1
1 2 2

输出

-1

分析：

思路，bfs加传送器，所以考虑到传送距离和路程花费时间，所以当tm[i][j]>=0还不能满足跳过的条件，还有判断是否已经是最优值，如果tm[p.x][p.y]+time>tm[a][b]就跳过。

代码：

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
ll n,m,k;
char g[3002][3002];
vector<vector<ll>> tm(3002,vector<ll>(3002,-1));
ll jl[3002][3002];
ll dx[]={0,1,0,-1},dy[]={1,0,-1,0};
struct fx{ll x,y; 
};
queue<fx> q;
ll hh=0,tt=-1;
void bfs()
{while(!q.empty()){auto p=q.front();q.pop();for(ll i=0;i<4;i++){ll a,b;ll ts=1;if(jl[p.x][p.y])//如果是弹射器，那个下一步花费时间为零，ts=0a=p.x+dx[i]*jl[p.x][p.y],b=p.y+dy[i]*jl[p.x][p.y],ts=0;else a=p.x+dx[i],b=p.y+dy[i];if(a<1||a>n||b<1||b>m)continue;if(g[a][b]=='#')continue;if(tm[a][b]>=0&&tm[a][b]<=tm[p.x][p.y]+ts)continue;//在弹射器的加入下，可能有更优解if(!jl[p.x][p.y])tm[a][b]=tm[p.x][p.y]+1;else if(jl[p.x][p.y])tm[a][b]=tm[p.x][p.y];q.push({a,b});}}
}
void solve()
{cin>>n>>m;for(ll i=1;i<=n;i++){for(ll j=1;j<=m;j++){cin>>g[i][j];}}for(ll i=1;i<=n;i++)for(ll j=1;j<=m;j++)jl[i][j]=0;cin>>k;for(ll i=0;i<k;i++){ll x,y,w;cin>>x>>y>>w;jl[x][y]=w;}q.push({1,1});tm[1][1]=0;bfs();cout<<tm[n][m];
}
int main()
{ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);ll t=1;while(t--)solve();return 0;
}