查看原帖
1082999
jfls211320zhr楼主2024/10/18 15:32
#include<bits/stdc++.h>
using namespace std;
int sti(string s){
	int r=0,n=s.size();
	for(int i=0;i<n;i++){
		r*=10;
		r+=s[i]-48;
	}
	return r;
}
int sdx[]={1,0,-1,0};
int sdy[]={0,1,0,-1};
int dx[]={1,1,0,-1,-1,-1,0,1};
int dy[]={0,1,1,1,0,-1,-1,-1};
int g[353][353];
int step[353][353];
int st1[353][353];
int st2[353][353];
bool vis[353][353];
queue<pair<pair<int,int>,int> >q;
int n,m,c1,c2,d,stx,sty,edx,edy;
void ctrl(int x,int y,int stp){
	memset(vis,0,sizeof(vis));
	int tx,ty,ts,xx,yy;
	g[x][y]=2;
	vis[x][y]=1;
	q.push({{x,y},stp-1});
	while(q.size()){
		tx=q.front().first.first;
		ty=q.front().first.second;
		ts=q.front().second;
		q.pop();
		if(ts==0)continue;
		for(int i=0;i<4;i++){
			xx=tx+dx[i];
			yy=ty+dy[i];
			if(xx<1||yy<1||xx>n||yy>m||vis[xx][yy])continue;
			g[xx][yy]=max(g[xx][yy],1);
			vis[xx][yy]=1;
			q.push({{xx,yy},ts-1});
		}
	}
	return;
}
queue<pair<pair<int,int>,pair<int,int> > >qu;
void bfs(){
	memset(vis,0,sizeof(vis));
	memset(step,63,sizeof(step));
	vis[stx][sty]=1;
	step[stx][sty]=0;
	st1[stx][sty]=c1;
	st2[stx][sty]=c2;
	qu.push({{stx,sty},{c1,c2}});
	int x,y,t1,t2,xx,yy;
	while(qu.size()){
		x=qu.front().first.first;
		y=qu.front().first.second;
		t1=qu.front().second.first;
		t2=qu.front().second.second;
		qu.pop();
		for(int i=0;i<8;i++){
			xx=x+dx[i];
			yy=y+dy[i];
			if(xx<1||yy<1||xx>n||yy>n||g[xx][yy]||vis[xx][yy])continue;
			vis[xx][yy]=1;
			step[xx][yy]=step[x][y]+1;
			st1[xx][yy]=st1[x][y];
			st2[xx][yy]=st2[x][y];
			qu.push({{xx,yy},{t1,t2}});
		}
		if(t1){
			for(int i=0;i<8;i++){
				xx=x+dx[i];
				yy=y+dy[i];
				if(xx<1||yy<1||xx>n||yy>n||g[xx][yy]==2||vis[xx][yy])continue;
				vis[xx][yy]=1;
				step[xx][yy]=step[x][y]+1;
				st1[xx][yy]=st1[x][y]-1;
				st2[xx][yy]=st2[x][y];
				qu.push({{xx,yy},{t1-1,t2}});
			}
		}
		if(t2){
			for(int i=0;i<4;i++){
				xx=x+d*sdx[i];
				yy=y+d*sdy[i];
				if(xx<1||yy<1||xx>n||yy>n||g[xx][yy]||vis[xx][yy])continue;
				vis[xx][yy]=1;
				step[xx][yy]=step[x][y]+1;
				st1[xx][yy]=st1[x][y];
				st2[xx][yy]=st2[x][y]-1;
				qu.push({{xx,yy},{t1,t2-1}});
			}
		}
		if(t1&&t2){
			for(int i=0;i<4;i++){
				xx=x+d*sdx[i];
				yy=y+d*sdy[i];
				if(xx<1||yy<1||xx>n||yy>n||g[xx][yy]==2||vis[xx][yy])continue;
				vis[xx][yy]=1;
				step[xx][yy]=step[x][y]+1;
				st1[xx][yy]=st1[x][y]-1;
				st2[xx][yy]=st2[x][y]-1;
				qu.push({{xx,yy},{t1-1,t2-1}});
			}
		}
	}
	return;
}
string s;
int main(){
	scanf("%d %d %d %d %d",&n,&m,&c1,&c2,&d);
	for(int i=1;i<=n;i++){
		for(int ii=1;ii<=m;ii++){
			cin>>s;
			if(s=="S"){
				stx=i;
				sty=ii;
			}
			else if(s=="T"){
				edx=i;
				edy=ii;
			}
			else if(s!=".")ctrl(i,ii,sti(s));
		}
	}
	bfs();
	if(step[edx][edy]==0x3f3f3f3f)printf("-1");
	else printf("%d %d %d",step[edx][edy],c1-st1[edx][edy],c2-st2[edx][edy]);
	return 0;
}
2024/10/18 15:32
加载中...