75pts,WA on #13,14,15,20,QAQ
查看原帖
75pts,WA on #13,14,15,20,QAQ
1335720
TC_QD楼主2024/7/20 18:17

QAQ

#include <bits/stdc++.h>
//#pragma GCC optimize(2)
using namespace std;
const int dx[8]={-1,0,1,0,-1,1,1,-1},
		  dy[8]={0,1,0,-1,1,1,-1,-1};
int n,m,c1,c2,dist,sx,sy,tx,ty;
int cov[500][500],d[500][500][20][20];
bool pes[500][500],vis[500][500][20][20];
struct QAQ{
	int x,y,u1,u2;
	QAQ(int v1,int v2,int v3,int v4):
		x(v1),y(v2),u1(v3),u2(v4) {}
};
bool in(int x,int y)
{
	return 1<=x && x<=n && 1<=y && y<=m;
}
void bfs()
{
	queue <QAQ> q;
	d[sx][sy][0][0]=0;
	vis[sx][sy][0][0]=true;
	q.push((QAQ){sx,sy,0,0});
	while (q.size())
	{
		QAQ u=q.front();
		q.pop();
		for (int i=0;i<8;i++)
		{
			int nx=u.x+dx[i];
			int ny=u.y+dy[i];
			if (in(nx,ny) && !pes[nx][ny])
			{
				if (cov[nx][ny])
				{
					if (u.u1+1<=c1 && !vis[nx][ny][u.u1+1][u.u2])
					{
						d[nx][ny][u.u1+1][u.u2]=d[u.x][u.y][u.u1][u.u2]+1;
						vis[nx][ny][u.u1+1][u.u2]=true;
						q.push((QAQ){nx,ny,u.u1+1,u.u2});
					}
				}
				else
				{
					if (!vis[nx][ny][u.u1][u.u2])
					{
						d[nx][ny][u.u1][u.u2]=d[u.x][u.y][u.u1][u.u2]+1;
						vis[nx][ny][u.u1][u.u2]=true;
						q.push((QAQ){nx,ny,u.u1,u.u2});
					}
				}
			}
		}
		if (u.u2+1<=c2)
		{
			for (int i=0;i<4;i++)
			{
				int nx=u.x+dx[i]*dist;
				int ny=u.y+dy[i]*dist;
				if (in(nx,ny) && !pes[nx][ny])
				{
					if (cov[nx][ny])
					{
						if (u.u1+1<=c1 && !vis[nx][ny][u.u1+1][u.u2+1])
						{
							d[nx][ny][u.u1+1][u.u2+1]=d[u.x][u.y][u.u1][u.u2]+1;
							vis[nx][ny][u.u1+1][u.u2+1]=true;
							q.push((QAQ){nx,ny,u.u1+1,u.u2+1});
						}
					}
					else
					{
						if (!vis[nx][ny][u.u1][u.u2+1])
						{
							d[nx][ny][u.u1][u.u2+1]=d[u.x][u.y][u.u1][u.u2]+1;
							vis[nx][ny][u.u1][u.u2+1]=true;
							q.push((QAQ){nx,ny,u.u1,u.u2+1});
						}
					}
				}
			}
		}	
	}
	return;
}
int main()
{
	cin>>n>>m>>c1>>c2>>dist;
	char s[4];
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++)
		{
			scanf("%s",s);
			if (s[0]=='S')
			{
				sx=i;
				sy=j;
			}
			else if (s[0]=='T')
			{
				tx=i;
				ty=j;
			}
			else if (s[0]!='.')
			{
				pes[i][j]=true;
				int len=strlen(s),num=0;
				for (int k=0;k<len;k++)
				{
					num=num*10+s[k]-'0';
				}
				for (int t=max(1,i-num+1);t<=min(n,i+num-1);t++)
				{
					int l=max(1,j-num+1+abs(i-t)),
						r=min(m,j+num-1-abs(i-t));
					cov[t][l]++;
					cov[t][r+1]--;
				}
			}
		}
	}
	for (int i=1;i<=n;i++)
	{
		for (int j=2;j<=m;j++)
		{
			cov[i][j]+=cov[i][j-1];
		}
	}
	bfs();
	int t=n*m,u1,u2;
	for (int i=0;i<=c1+c2;i++)
	{
		for (int j=0;j<=i;j++)
		{
			if (vis[tx][ty][j][i] && d[tx][ty][j][i]<t)
			{
				t=d[tx][ty][j][i];
				u1=j;
				u2=i-j;
			}
		}
	}
	if (t==n*m)
	{
		cout<<-1;
	}
	else
	{
		cout<<t<<" "<<u1<<" "<<u2;
	}
 	return 0;
}
2024/7/20 18:17
加载中...