链接:https://ac.nowcoder.com/acm/contest/23156/1018
来源:牛客网
有多组数据。对于每组数据: 第一行有三个整数n,m,q(2≤ n,m≤300,0≤ q ≤ 1000)。 接下来是一个n行m列的矩阵,表示迷宫。 最后q行,每行四个整数x1
,y1
,x2
,y2
(0≤ x1
,x2
< n,0≤ y1
,y2
< m),表示一个传送阵的入口在x1
行y1
列,出口在x2
行y2
列。
如果小明能够活着到达目的地,则输出最短时间,否则输出-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;
}
/*样例区
*/
//------------------------------------------------------------