悬关!!90分(O_O)
查看原帖
悬关!!90分(O_O)
858275
youshuohan楼主2023/8/31 18:41
#include <bits/stdc++.h>
using namespace std;
struct node
{
	int x,y,ti,steal,tran;
};
queue<node>q;
int a[400][400],dx[8]={0,0,-1,1,1,1,-1,-1},dy[8]={1,-1,0,0,1,-1,1,-1},n,m,c1,c2,d,s,ex,ey;
bool check(int x,int y)
{
	if(x>0&&y>0&&x<=n&&y<=m) return 1;
	return 0;
}
void guard(int x,int y,int l,int w,int e)
{
	for(int i=0;i<4;i++)
	{
		int tx=x+dx[i],ty=y+dy[i];
		if(check(tx,ty)&&a[tx][ty]==0&&(abs(tx-w)+abs(ty-e))<l) a[tx][ty]=-l,guard(tx,ty,l,w,e);
	}
}
bool vis[400][400][20][20];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	string st;
	cin>>n>>m>>c1>>c2>>d;
	memset(vis,0,sizeof(vis)),memset(a,0,sizeof(a));
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>st;
			if(st=="T") ex=i,ey=j;
			else if(st=="S") q.push(node{i,j,0,0,0}),vis[i][j][0][0]=1;
			else if(st!=".")
			{
				s=0;
				for(int k=0;k<st.size();k++) s=s*10+st[k]-48;
				a[i][j]=s,guard(i,j,s,i,j);
			}
		}
	}
	int x,y,t,_1,_2,tx,ty,ans=INT_MAX,a_1=0x3f,a_2=0x3f;
	bool f=0;
	while(!q.empty())
	{
		x=q.front().x,y=q.front().y,t=q.front().ti,_1=q.front().steal,_2=q.front().tran;
//		cout<<ans<<' '<<a_1<<' '<<a_2<<endl;
		if(x==ex&&y==ey)
		{
			if(ans>t) ans=t,a_1=_1,a_2=_2;
			else if(ans==t&&(a_1+a_2>_1+_2||(a_1+a_2==_1+_2&&_1<a_1))) ans=t,a_1=_1,a_2=_2;
			q.pop();
			continue;
		}
		for(int i=0;i<8;i++)
		{
			tx=x+dx[i],ty=y+dy[i];
			if(check(tx,ty)&&a[tx][ty]==0&&!vis[tx][ty][_1][_2])
			{
				if(tx==ex&&ty==ey)
				{
					if(!f) f=1;
//					else if(t+1>ans) break;
					q.push(node{tx,ty,t+1,_1,_2});
				}
				if(!f) vis[tx][ty][_1][_2]=1,q.push(node{tx,ty,t+1,_1,_2});
			}
		}
		for(int i=0;i<4;i++)
		{
			tx=x+dx[i]*d,ty=y+dy[i]*d;
			if(check(tx,ty)&&a[tx][ty]==0&&c2-_2&&!vis[tx][ty][_1][_2+1])
			{
				if(tx==ex&&ty==ey)
				{
					if(!f) f=1;
//					else if(t+1>ans) break;
					q.push(node{tx,ty,t+1,_1,_2+1});
				}
				if(!f) vis[tx][ty][_1][_2+1]=1,q.push(node{tx,ty,t+1,_1,_2+1});
			}
		}
		for(int i=0;i<8;i++)
		{
			tx=x+dx[i],ty=y+dy[i];
			if(check(tx,ty)&&a[tx][ty]<0&&c1-_1&&!vis[tx][ty][_1+1][_2])
			{
				if(tx==ex&&ty==ey)
				{
					if(!f) f=1;
//					else if(t+1>ans) break;
					q.push(node{tx,ty,t+1,_1+1,_2});
				}
				if(!f) vis[tx][ty][_1+1][_2]=1,q.push(node{tx,ty,t+1,_1+1,_2});
			}
		}
		for(int i=0;i<4;i++)
		{
			tx=x+dx[i]*d,ty=y+dy[i]*d;
			if(check(tx,ty)&&a[tx][ty]<0&&c1-_1&&c2-_2&&!vis[tx][ty][_1+1][_2+1])
			{
				if(tx==ex&&ty==ey)
				{
					if(!f) f=1;
//					else if(t+1>ans) break;
					q.push(node{tx,ty,t+1,_1+1,_2+1});
				}
				if(!f) vis[tx][ty][_1+1][_2+1]=1,q.push(node{tx,ty,t+1,_1+1,_2+1});
			}
		}
		q.pop();
	}
	if(!f) cout<<-1;
	else cout<<ans<<' '<<a_1<<' '<<a_2;
	return 0;
}
2023/8/31 18:41
加载中...