(⊙o⊙)…,被针对了?本地能过,提交就错
查看原帖
(⊙o⊙)…,被针对了?本地能过,提交就错
404202
acacac123楼主2022/8/2 20:16
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,M,c1,c2,d,m[355][355],i,j,qx,qy,zx,zy,k,CF[355][355],dx[]= {0,0,0,1,-1,1,1,-1,-1},dy[]= {0,1,-1,0,0,1,-1,-1,1},ga[355][355][25][25],jj;
bool VS[355][355];
char c[3];
struct JK
{
	ll line;
	ll list;
	ll cost;
	ll invisible;
	ll blink;
};
queue<JK> QW;
JK cmp(JK f,JK s)
{
	if(f.cost!=s.cost)
	{
		return f.cost<s.cost?f:s;
	}
	else
	{
		ll f1=f.invisible+f.blink;
		ll s1=s.blink+s.invisible;
		if(f1!=s1)
		{
			return f1<s1?f:s;
		}
		else
		{
			return f.invisible<s.invisible?f:s;
		}
	}
}
JK e=(JK){0,0,1000000000,1000000000,1000000000};
void look_up(ll x,ll y,ll sc)
{
	ll ii;
	for(ii=0; ii<=sc; ii++)
	{
		CF[max(x-ii,(ll)1)][max(y-(k-ii),(ll)1)]++;
		CF[max(x-ii,(ll)1)][min(y+(k-ii),M)+1]--;
		CF[min((x+ii),n)][max(y-(k-ii),(ll)1)]++;
		CF[min(x+ii,n)][min(y+(k-ii),M)+1]--;
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin>>n>>M>>c1>>c2>>d;
	for(i=1; i<=n; i++)
	{
		for(j=1; j<=M; j++)
		{
			scanf("%s",c);
			if(c[0]=='S')
			{
				qx=i,qy=j;
				m[i][j]=-1;
				QW.push((JK){qx,qy,0,0,0});
				ga[i][j][0][0]=1;
			}
			else 
			{
				if(c[0]=='T')
				{
					zx=i;
					zy=j;
					m[i][j]=-2;
				}
				else 
				{
					if(c[0]=='.')
					{
						m[i][j]=0;
					}
					else
					{
						ll x=0;
						for(ll ii=0; ii<strlen(c); ii++)
						{
							x=(x<<1)+(x<<3)+(c[ii]^'0');
						}	
						m[i][j]=x;
						look_up(i,j,x-1);
					}
				}
			}	
		}
	}
	for(i=1; i<=n; i++)
	{
		ll sum=0;
		for(j=1; j<=M; j++)
		{
			sum+=CF[i][j];
			if(sum>0)
			{
				VS[i][j]=1;
			}
		}
	}
	while(QW.size()!=0)
	{
//		cout<<++jj<<endl;
		JK six=QW.front();
		QW.pop();
		if(six.cost>e.cost)
		{
			continue;
		}
		if(six.line==zx&&six.list==zy)
		{
			e=cmp(e,six);
			continue;
		}
		for(i=1; i<=8; i++)
		{
			ll sx=six.line+dx[i];
			ll sy=six.list+dy[i];
			if(sx>0&&sx<=n&&sy>0&&sy<=M&&m[sx][sy]<=0)
			{
				if(VS[sx][sy]==1)
				{
					if(ga[sx][sy][six.invisible+1][six.blink]==1||six.invisible+1>c1)
					{
						continue;
					}
					ga[sx][sy][six.invisible+1][six.blink]=1;
					QW.push((JK){sx,sy,six.cost+1,six.invisible+1,six.blink});
				}
				else
				{
					if(ga[sx][sy][six.invisible][six.blink]==1)
					{
						continue;
					}
					ga[sx][sy][six.invisible][six.blink]=1;
					QW.push((JK){sx,sy,six.cost+1,six.invisible,six.blink});
				}
			}
		}
		if(six.blink+1<=c2)
		{
			for(i=1; i<=4; i++)
			{
				ll ex=six.line+d*dx[i];
				ll ey=six.list+d*dy[i];
				if(ex>0&&ex<=n&&ey>0&&ey<=M&&m[ex][ey]<=0)
				{
					if(VS[ex][ey]==1)
					{
						if(ga[ex][ey][six.invisible+1][six.blink+1]==1||six.invisible+1>c1)
						{
							continue;
						}
						ga[ex][ey][six.invisible+1][six.blink+1]=1;
						QW.push((JK){ex,ey,six.cost+1,six.invisible+1,six.blink+1});
					}
					else
					{
						if(ga[ex][ey][six.invisible][six.blink+1]==1)
						{
							continue;
						}
						ga[ex][ey][six.invisible][six.blink+1]=1;
						QW.push((JK){ex,ey,six.cost+1,six.invisible,six.blink+1});
					}
				}
			}
		}
	}
	if(e.cost==1000000000)
	{
		cout<<-1;
		return 0;
	}
	cout<<e.cost<<" "<<e.invisible<<" "<<e.blink;
	return 0;
}
2022/8/2 20:16
加载中...