玄学问题
查看原帖
玄学问题
288716
lzqy_楼主2021/3/29 13:48

rt,我代码不开O2七彩评测,开了O2就85……

同学的代码也是这个情况。

是UB吗/yiw

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=251;
inline int read()
{
	register int x=0;
	register char c=getchar();
	for(;!(c>='0'&&c<='9');c=getchar());
	for(;c>='0'&&c<='9';c=getchar())
		x=(x<<1)+(x<<3)+c-'0';
	return x;
}
int a[maxn][maxn];
int n,Mm,Q;
struct pp
{
	int x,y;
};
bool operator ==(pp a,pp b)
{
	return (a.x==b.x&&a.y==b.y);
}
struct ppp
{
	pp one,two;
}M;
queue<ppp>q;
int p[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
map<ll,bool>m;
int k[31][31][31][31];
pp run(pp M,int i)
{
	register int x=M.x,y=M.y;
	while(a[x+p[i][0]][y+p[i][1]]==0) x+=p[i][0],y+=p[i][1];
	M.x=x,M.y=y;
	return M;
}
ll hash(ppp M)
{
	return M.one.x+M.one.y*n+M.two.x*n*n+M.two.y*1ll*n*n*n;
}
int bfs()
{
	while(!q.empty()) q.pop();
	q.push(M);
	ppp t;
	register int len,ans=0;
	register ll H;
	m.clear();
	while(!q.empty())
	{
		len=q.size();
		for(register int i=1;i<=len;i++)
		{
			t=q.front(),q.pop();
			if(t.one==t.two)
				return ans;
			for(register int j=0;j<4;j++)
			{
				M.one=run(t.one,j),M.two=run(t.two,j);
				H=hash(M);
				if(m[H]==0)
				q.push(M),m[H]=1;
			}
		}
		ans++;
		if(ans>n)
		     return -1;
	}
	return -1;
}
int main()
{
	register int x,y;
	n=read(),Mm=read(),Q=read();
	ppp mmm;
	while(Mm--)
		x=read(),y=read(),a[x][y]=1;
	for(register int i=0;i<=n+1;i++)
		a[0][i]=1,a[n+1][i]=1,a[i][0]=1,a[i][n+1]=1;
	if(n>30)
		while(Q--)
		{
			M.one.x=read(),M.one.y=read(),M.two.x=read(),M.two.y=read();
			printf("%d\n",bfs());
		}
	else
		while(Q--)
		{
			M.one.x=read(),M.one.y=read(),M.two.x=read(),M.two.y=read();
			mmm=M;
			if(k[M.one.x][M.one.y][M.two.x][M.two.y]==0)
				k[M.one.x][M.one.y][M.two.x][M.two.y]=bfs();
			printf("%d\n",k[mmm.one.x][mmm.one.y][mmm.two.x][mmm.two.y]);	
		}
	return 0;
}

2021/3/29 13:48
加载中...