C++(clang++ 11.0.1) 解法, 执行用时: 14ms, 内存消耗: 516K, 提交时间: 2022-10-01 19:47:54

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+10;
int n,m;
int xs,ys;
char mp[107][107];

struct node{
	int x,y,step,c;
	bool operator < (const node &rhs) const {
		return step>rhs.step;
	}
};

int d[]={0,-1,0,1,0};
int bfs(){
	int book[2][107][107]={0};
    priority_queue<node> q;
	q.push({xs,ys,0,0});
	
	while(q.size()){
		node cur=q.top();
		q.pop();
		if(book[cur.c][cur.x][cur.y]) continue;
		book[cur.c][cur.x][cur.y]=1;
		if(mp[cur.x][cur.y]=='X')	return cur.step;
		
		for(int i=0;i<4;i++){
			int rx=cur.x+d[i];
			int ry=cur.y+d[i+1];
			int c=cur.c|(mp[rx][ry]=='C');
			if(rx<1||rx>n||ry<1||ry>n||mp[rx][ry]=='O'||book[c][rx][ry]) continue;
			q.push({rx,ry,cur.step+2-cur.c,c});
		}
		
	}
	return 1000000010;
}

int main(){
	int t;
	scanf("%d",&t);
	
	while(t--){
		scanf("%d%d",&n,&m);
		
		for(int i=1;i<=n;i++) scanf("%s",mp[i]+1);
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(mp[i][j]=='S') xs=i,ys=j;
			}
		}
		
		int ans=bfs();
		if(ans>m) printf("NO\n");
		else printf("YES\n%d\n",ans);
	}
}

C++(g++ 7.5.0)(g++7.5.0) 解法, 执行用时: 17ms, 内存消耗: 760K, 提交时间: 2023-07-30 17:39:39

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
char mp[1010][1010];
ll t,n,k,vis[105][105][3],x,y,xx,yy,p,ans=0;
ll dx[][2]={0,1,0,-1,1,0,-1,0};
struct stu{
	ll x,y,step,steep;
	bool operator<(const stu& a)const{
		return step > a.step;
	}
}a;
void BFS(){
	priority_queue<stu>q;
	while(!q.empty())q.pop();
	a.x=x;a.y=y;
	a.step=0;a.steep=2;
	vis[a.x][a.y][a.steep]=1;
	q.push(a);
	while(!q.empty()){
		a=q.top();q.pop();
		if(mp[a.x][a.y]=='X'&& a.steep <= k){
			cout<<"YES"<<endl<<a.step<<endl;return;
		}
		for(ll i=0;i<4;i++){
			xx=a.x+dx[i][0];yy=a.y+dx[i][1];
			p=a.steep;
			if(xx<1||yy<1||xx>n||yy>n||vis[xx][yy][p]||mp[xx][yy]=='O')continue;
			vis[xx][yy][p]=1;
			ans=a.step+p;
			if(mp[xx][yy]=='C')p=1;
			if(ans<=k)q.push({xx,yy,ans,p});
		}
	}
	cout<<"NO"<<endl;
}
int main(){
	cin>>t;
	while(t--){
		memset(vis,0,sizeof(vis));
		cin>>n>>k;
		for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>mp[i][j];
		for(int i=1;i<=n;i++)for(int j=1; j<=n;j++)if(mp[i][j]=='S')x=i,y=j;
		BFS();
	}
	return 0;
}