1019 wyh的吃鸡 bfs+优先队列

链接：https://ac.nowcoder.com/acm/problem/15445
来源：牛客网

题目描述

最近吃鸡游戏非常火，你们wyh学长也在玩这款游戏，这款游戏有一个非常重要的过程，就是要跑到安全区内，否则就会中毒持续消耗血量，我们这个问题简化如下

假设地图为n*n的一个图，图中有且仅有一块X的联通快代表安全区域，有一个起点S代表缩圈的时候的起点，图中C代表的是车（保证车的数量小于等于100），标记为.的代表空地，可以任意通过，O代表障碍物不能通过。每次没有车的时候2s可以走一个格（只能走自己的上下左右4个方向），有车的话时间为1s走一个格

现在告诉你最多能坚持的时间为t秒，问你在t秒内（含t秒）能否从s点到达安全区域，能的话输出YES，并且输出最短时间，不能的话输出NO

输入描述:

输入第一行一个整数T(1<=T<=10)
接下来有T组测试数据，每组测试数据输入2个数n和k(1<=n<=100,1<=k<=10^9)
接下来n行，每行n个字符，代表对应的n*n的地图，每个字符都是上面的一种，并且保证只有一个起点，只有一块安全区域。

输出描述:

对于每组测试数据，先输出能否到达，能的话输出YES，然后换行输出最短时间，如果不能的话直接输出NO

示例1

输入

复制 3<br />2 3<br />.X<br />S.<br />2 3<br />.X<br />SC<br />2 4<br />.X<br />S.

3
2 3
.X
S.
2 3
.X
SC
2 4
.X
S.

输出

复制 NO<br />YES<br />3<br />YES<br />4

NO
YES
3
YES
4

分析

一开始就想到有限队列来处理
但是感觉和之前那种一次性跳跃的优先队列又不大一样
但看了多篇题解，才发现差不多还是看走了多少距离来逐步更新
只不过存的vis要变一下，一种是有车走过这个位置一种是没车走过这个位置
突然发现不是速度是2
而是一秒走两格。。
然后稍作修改，一直错误，不晓得为啥，想去看题解
然后发现犯了概念性错误：在还没走到有车的位置，就开着车过去了（就是速度改得太早了）
但是tle，最后发现还是上面那个概念性错误的细节问题，跳出来的时机错了。。优化要小心

*/

//————————-代码—————————-

#define int LL
const int N = 110;

struct Q {
    int x,y;
    int step;bool flag;
    bool operator<(const Q & t) const {
        return step > t.step;
    }
};
PII st,ed;
int vis[2][N][N];
char mp[N][N];
priority_queue<Q> q;
int n,k;

int bfs() {
    while(q.size()) {
        auto t = q.top();q.pop();//得到Q
        int x = t.x ,y = t.y ,step = t.step;bool flag = t.flag;
        if(mp[x][y] == ‘X’ && step <= k)return step ;
        fo(i,0,3) {
            bool ff = flag;int hh = 2;if(flag) hh = 1;
            int xx = x + dx[i] ,yy = y + dy[i] ;
            if(mp[xx][yy] == ‘O’ || xx < 1 || yy < 1 || xx > n || yy > n || vis[flag][xx][yy]) continue;
            vis[ff][xx][yy] = 1;
            if(mp[xx][yy] == ‘C’) ff = 1;
            if(step + hh <= k )q.push({xx,yy,step + hh,ff});
        }
    }
    return -1;
}

void solve()
{
    while(q.size()) q.pop();
    cin>>n>>k;
    fo(i,1,n) fo(j,1,n) {
        cin>>mp[i][j];if(mp[i][j] == ‘S’)st = {i,j};
    }
    q.push({st.x,st.y,0,0});
    memset(vis,0,sizeof vis);
    vis[0][st.x][st.y] = true;
    int x = bfs();
    if(x == -1 ) {NO;}
    else {YES; cout<<x<<endl;}
}

signed main(){
    clapping();TLE;
    
    int t;cin>>t;while(t — )
    solve();
//    {solve(); }
    return 0;
}

/*样例区

*/

//————————————————————