Java教程

1018 maze 优先队列+bfs

本文主要是介绍1018 maze 优先队列+bfs,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

链接: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;
}

/*样例区


*/

//------------------------------------------------------------

这篇关于1018 maze 优先队列+bfs的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!