这题的数据范围是不是有问题?
查看原帖
这题的数据范围是不是有问题?
494699
卷王慢即快楼主2022/4/7 21:33

这题的数据范围是300,我就开了301的数组,但是RE了,至少要改成381才能过,这是为什么?蒟蒻表示不懂。。。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
struct node {
	int x,y;
};
queue<node>Q;
int ans[310][310],death[310][310];
int work[4][2]={{0,1},{0,-1},{-1,0},{1,0}};
int main()
{
	int n;
	cin>>n;
	memset(death,0x7f,sizeof(death));
	memset(ans,-1,sizeof(ans));
	for(int i=0;i<n;i++)
	{
		int x,y,t;
		cin>>x>>y>>t;
#define MIN(x,y,t) if(x>=0 && y>=0) death[x][y]=min(death[x][y],t);
		MIN(x,y,t);
		for(int j=0;j<4;j++)
			MIN(x+work[j][0],y+work[j][1],t);
	}
	Q.push((node){0,0});
	ans[0][0]=0;
	while(!Q.empty())
	{
		node u=Q.front();
		Q.pop();
		int ux=u.x,uy=u.y;
		for(int i=0;i<4;i++)
		{
			int r=ux+work[i][0],s=uy+work[i][1];
			if(r<0 || s<0 || ans[r][s]!=-1 || ans[ux][uy]+1
			>=death[r][s]) continue;
			ans[r][s]=ans[ux][uy]+1;
			Q.push((node){r,s});
		}
	}
	int a=1000000;
	for(int i=0;i<=305;i++)
		for(int j=0;j<=305;j++)
			if(ans[i][j]!=-1 && death[i][j]>1000)
				a=min(a,ans[i][j]);
	if(a!=1000000) cout<<a;
	else cout<<"-1";
	return 0;
}
2022/4/7 21:33
加载中...