链接：https://ac.nowcoder.com/acm/contest/23156/1018
来源：牛客网
题目描述
小明来到一个由n x m个格子组成的迷宫，有些格子是陷阱，用’#’表示，小明进入陷阱就会死亡，’.’表示没有陷阱。小明所在的位置用’S’表示，目的地用’T’表示。
小明只能向上下左右相邻的格子移动，每移动一次花费1秒。
有q个单向传送阵，每个传送阵各有一个入口和一个出口，入口和出口都在迷宫的格子里，当走到或被传送到一个有传送阵入口的格子时，小明可以选择是否开启传送阵。如果开启传送阵,小明就会被传送到出口对应的格子里，这个过程会花费3秒；如果不开启传送阵，将不会发生任何事情，小明可以继续向上下左右四个方向移动。
一个格子可能既有多个入口，又有多个出口，小明可以选择任意一个入口开启传送阵。使用传送阵是非常危险的，因为有的传送阵的出口在陷阱里，如果小明使用这样的传送阵，那他就会死亡。也有一些传送阵的入口在陷阱里，这样的传送阵是没有用的，因为小明不能活着进入。请告诉小明活着到达目的地的最短时间。
输入描述:
有多组数据。对于每组数据：
第一行有三个整数n,m,q(2≤ n,m≤300,0≤ q ≤ 1000)。
接下来是一个n行m列的矩阵，表示迷宫。
最后q行，每行四个整数x
1
,y
1
,x
2
,y
2
(0≤ x
1
,x
2
< n,0≤ y
1
,y
2
< m)，表示一个传送阵的入口在x
1
行y
1
列，出口在x
2
行y
2
列。
输出描述:
如果小明能够活着到达目的地，则输出最短时间，否则输出-1。
示例1
输入
5 5 1 ..S.. ..... .###. ..... ..T.. 1 2 3 3 5 5 1 ..S.. ..... .###. ..... ..T.. 3 3 1 2 5 5 1 S.#.. ..#.. ###.. ..... ....T 0 1 0 2 4 4 2 S#.T .#.# .#.# .#.# 0 0 0 3 2 0 2 2
输出
6 8 -1 3
备注:
坐标从0开始
分析
bfs + 优先队列
1.//一开始感觉直接一个简单bfs就好了
2.//后来发现原来一个位置有多个传送阵。。就不知道该用什么数据结构存储了，而且不知道距离最短该怎么表示，那个时候在我印象里，bfs还是一个一个相邻的点向外扩展
3.然后看了雨巨的课，才知道bfs 一开始并不一定是用队列存储，队列只是保证了 bfs 向最近的点扩展的特性，而且bfs 有找最短路的特性，我们只需要用优先队列存储下一个可以到达的步数最短的点
就可以找到起点到终点的最短路径
4.但是还是不太会用优先队列写，属于是队列写习惯了，看了题解才知道，可以用大根堆，然后再结构体里面写一个单调递减，属于是负负得正得到一个存储 最小步数 的优先队列
5.不过题解里还是又不一样的地方，比如判断是在加入队列之后才判断，确实这样写代码少一点，因为有两种入队操作，一个传送阵，一个上下左右，但是时间复杂度也确实会多一点
6.然后抄了一遍，自己又写了一遍，就是a不了，后来发现，第一个t.step 写成 t.x，第二个<m 写成 < n，第三个忘记把优先队列清空
7.ac
#include<bits/stdc++.h>
#define TLE ios::sync_with_stdio(0),cin.tie(0)
#define endl “/n”
#define pb push_back
#define gg exit(0);
#define bd cout<<“debug”<<endl;
#define x first
#define None cout<<-1<<endl;
#define y second
#define all(a) a.begin(),a.end()
#define alll(a) a.begin()+1,a.end()
#define db(x) cout<<#x<<‘:'<<x<<endl;
#define dbb(i,a,b) cout<<#i<<‘:'<<i<<‘ ‘<<#a<<‘:'<<a<<‘ ‘<<#b<<‘:'<<b<<endl;
#define rt return;
#define YES cout<<“YES”<<endl;
#define NO cout<<“NO”<<endl;
#define V vector
#define fo(i,j,n) for(int i = j;i<=n;i++)
#define of(i,n,j) for(int i = n;i>=j;i–)
#define ent cout<<endl;
#define lowbit(x) (x&-x)
#define gcd(a,b) __gcd(a,b)
#define DEBUG 11243
using namespace std;
void clapping() {
#if DEBUG == 1
freopen(“a.in”,”r”,stdin);
freopen(“a.out”,”w”,stdout);
#endif
}
typedef pair<int,int> PII;
typedef long long LL;
int dx[] = {0,1,0,-1,1,-1,1,-1,0};
int dy[] = {1,0,-1,0,1,-1,-1,1,0};
/*文档区
*/
//————————-代码—————————-
//#define int LL
//一开始感觉直接一个简单bfs就好了
//后来发现原来一个位置有多个传送阵。。
//
const int N = 310;
PII st,ed;
struct Q {
int x,y,step;
bool operator<(const Q & s) const {
return step > s.step;
}
} ;
char mp[N][N];
bool vis[N][N];
V<PII> v[N][N];
int n,m,t;
priority_queue<Q> q;//大根堆，所以内部要把大的放到前面，才能变成小的在其那面
int bfs() {
while(q.size()) {
auto t = q.top();q.pop();//把大于m写成大于n了
if(t.x < 1 || t.y < 1 || t.x > n || t.y > m || vis[t.x][t.y] || mp[t.x][t.y] == ‘#’) continue;
if(t.x == ed.x && t.y == ed.y) return t.step;
vis[t.x][t.y] = true;
fo(i,0,3) q.push({t.x + dx[i],t.y + dy[i],t.step + 1});
for(auto u:v[t.x][t.y]) q.push({u.x,u.y,t.step + 3});//在这个不小心写成t.x了
} return -1;
}
void solve() {
while(cin>>n>>m>>t) {
while(q.size())q.pop();//少了这个
fo(i,1,n) {
fo(j,1,m) {
cin>>mp[i][j];
if(mp[i][j] == ‘S’) st = {i,j};
if(mp[i][j] == ‘T’) ed = {i,j};
v[i][j].clear();
vis[i][j] = 0;
}
} q.push({st.x,st.y,0});
fo(i,1,t) {
int a,b,c,d;cin>>a>>b>>c>>d;
a ++ ,b ++ ,c ++ ,d ++ ;
v[a][b].pb({c,d});
}
cout<<bfs()<<endl;
}
}
signed main(){
clapping();TLE;
// int t;cin>>t;while(t — )
solve();
// {solve(); }
return 0;
}
/*样例区
*/
//————————————————————
原创文章，作者：，如若转载，请注明出处：https://blog.ytso.com/270951.html