BFS模板题
坑点是不要入队的时候判断是否到达了终点,因为可能此时可能无车t+2大于另一条有车t+1的路线,导致答案错误
心得:对于改变地图状态的可用vis,改变自身状态的用dis.

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define endl '\n'
using namespace std;

int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
struct node{
    int x,y,c,t;
    bool operator<(const node&o)const{
        return t>o.t;
    }
};
int dis[105][105][2];
void solve() {
    memset(dis,0x3f,sizeof(dis));
    int n,k;cin>>n>>k;
    vector<vector<char>>mp(n,vector<char>(n));
    int x,y;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>mp[i][j];
            if(mp[i][j]=='S')x=i,y=j;
        }
    }
    priority_queue<node>q;
    q.push({x,y,0,0});
    dis[x][y][0]=0;
    while(q.size()){
        auto[x,y,c,t]=q.top();q.pop();
        if(mp[x][y]=='X'){
            cout<<"YES"<<endl;
            cout<<t<<endl;
            return;
        }
        for(int i=0;i<4;i++){
            int xx=x,yy=y,nc=c,nt=t;
            xx+=dx[i],yy+=dy[i];
            if(xx<0||xx>=n||yy<0||yy>=n||mp[xx][yy]=='O')continue;
            nt+=(nc==1?1:2);
            if(nt>k)continue;
            if(mp[xx][yy]=='C')nc=1;
            if(nt<dis[xx][yy][nc]){
                dis[xx][yy][nc]=nt;
                q.push({xx,yy,nc,nt});
            }
        }
    }
    cout<<"NO"<<endl;
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0);
    int t = 1;cin>>t;
    while (t--)solve();
    return 0;
}