典型的BFS+多维vis数组+优先队列问题
链接：https://ac.nowcoder.com/acm/contest/23156/1019
来源：牛客网

题目描述

最近吃鸡游戏非常火，你们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.本题题干中的t就是输入描述中的k
2.这里的S点表示起点，只有一个；但是X在题目的描述中是一块连通块，可能存在连在一起的多个X点（虽然这对下面的代码不影响）
类似于求最短路径-->BFS求解
这里主要的难点就是增加了车的选项
但是我们可以知道，如果当前位置有车，那一定是必选项；
举个例子
S..C..X
明显看出，车刚好顺路，必选
但是，如果是C.S.............X呢
可以看出，我们的最优解应该是S->C->X
问题来了，普通的BFS遍历过的点不能再被遍历，同时这一题也不能用回溯，如何解决这个问题呢？
这个时候，介绍一种常用的方法：多开一维vis数组，这个多开的一维用于记录有车和无车的情况。
什么意思呢？
比如说，无车时用vis[0][][]记录无车时遍历的位置，有车时用vis[1][][]记录有车时遍历的位置
为什么多开了一维vis数组，就可以避免上述情况的发生了呢？
因为我们可以知道，如果是单纯的走路，是不需要走到之前走过的点的。（BFS基本思想）
同理，如果是单纯的开车，是不需要开到之前开过的点的。（BFS基本思想）
那么，我们可以开一个visa[][]，用于记录单纯走路的情况，再开一个visb[][]，用于记录单纯开车的情况，当还在走路时，就用visa[][]遍历，一旦有车了，就用visb[][]遍历。
所以vis[2][][]，相当于就是把visa和visb合在一起了而已，其中vis[0][][]就表示visa[][]，vis[1][][]就表示visb[][]
这样，遍历问题就很好的解决了

最后有几点要注意的：1.记得每次都要初始化
2.可以开优先队列，根据时间升序排序，使得队列里第一个到终点的一定是时间最小的，避免增加查找次数

最后推荐一道类似的题目（虽然是DFS，但是也是用vis[][][]做的）：1020-CSL的校园卡_2021秋季算法入门班第六章习题：搜索与搜索剪枝
以及本人对于这篇题目写的题解：题解 | #CSL的校园卡#_牛客博客

至于具体实现，可以看下面的代码（含注释）
代码如下
#include<bits/stdc++.h>
using namespace std;
struct node{
    int x,y,times,iscar;
    bool operator<(const node &a)const{ //重载运算符
        return times>a.times;
    }
};
int car[102][102];
priority_queue<node>q;
int T,n,t,ans=-1;
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}}; //方向数组
char mp[102][102];
int vis[2][102][102]; //vis[0][][]表示无车，vis[1][][]表示有车 
void BFS(){ //BFS基本模板
    while(!q.empty()){
        node tmp=q.top();
        q.pop();
        if(mp[tmp.x][tmp.y]=='X'){
            ans=tmp.times; //获得答案
            return;
        }
        for(int i=0;i<4;i++){
            int iscar=0;
            int xx=tmp.x+dir[i][0];
            int yy=tmp.y+dir[i][1];
            if(xx<0 || yy<0 || xx>=n || yy>=n || vis[tmp.iscar][xx][yy] || mp[xx][yy]=='O') continue;
            vis[tmp.iscar][xx][yy]=1;
            if(car[xx][yy]) iscar=1; //如果有车，那么iscar的值记为1
            if(tmp.iscar){
                if(tmp.times<=t) q.push(node{xx,yy,tmp.times+1,1});
            }
            else{
                if(tmp.times<=t) q.push(node{xx,yy,tmp.times+2,iscar}); 
            }
        }
    }
}
int main(){
    scanf("%d",&T);
    while(T--){
        memset(mp,'\0',sizeof(mp));
        memset(car,0,sizeof(car));
        memset(vis,0,sizeof(vis));
        while(!q.empty()) q.pop();
        ans=-1;
        scanf("%d%d",&n,&t);
        for(int i=0;i<n;i++){
            scanf("%s",mp[i]);
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(mp[i][j]=='C'){
                    car[i][j]=1; //记录车所在的位置
                }
                if(mp[i][j]=='S'){
                    vis[0][i][j]=1;
                    q.push(node{i,j,0,0});
                }
            }
        }
        BFS();
        if(ans==-1 || ans>t){ //如果到不了或者是能到但是时间过长，输出NO
            printf("NO\n");
        }else{
            printf("YES\n");
            printf("%d\n",ans);
        }
    }
    return 0;
}