蚌埠住了纯BFS无SPFA(图论:我不到啊)优化拉满也能AC
查看原帖
蚌埠住了纯BFS无SPFA(图论:我不到啊)优化拉满也能AC
964886
RedSpiderLily楼主2023/8/8 16:48

先前是70pts,TLE6个点,使用了好兄弟提供的快读getchar()升级版、狠狠吸氧(O2)、C++20启动!后直接AC了

搞得我都不想学正解了

不过好像有点运气成分,最耗时的一个点988ms,千万别参考(确信)

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
#define gc p1==p2&&(p1=(p2=bul)+fread(bul,1,100000,stdin),p1==p2)?EOF:*p2++
static char bul[100000],*p1(bul),*p2(bul);
#define emax(a,b) (((a)>(b))?(a):(b))
template<typename stasis>
stasis getin(){
	char c=gc;
	bool judge=0;
	while(c<'0'||c>'9')
	{
		if(c=='-')judge=1;
		c=gc;
	}
	stasis sum=0;
	while(c>='0'&&c<='9')
	{
		sum=sum*10+(c-'0');
		c=gc;
	}
	return (judge)?-sum:sum;
}
template<typename chrono>
void getout(chrono x){
	if(x<0)
	{
		putchar('-');
		x*=-1;
	}
	if(x>=10)
	{
		getout(x/10);
		putchar('0'+(x%10));
	}
	else putchar('0'+x);
}
struct node{
	int mx,my,kx,ky;
	long long dep;
};
int n,m,_;
int gx,gy,sx,sy,ex,ey;
bool map[32][32];
bool judge[32][32][32][32];
int changex[5]={0,1,-1,0,0};
int changey[5]={0,0,0,1,-1};
long long bfs(){
	queue<node>q;
	q.push(node{sx,sy,gx,gy,0});
	judge[sx][sy][gx][gy]=1;
	while(q.empty()==0)
	{
		node temp=q.front();
		q.pop();
		int nowmx,nowmy,nowkx,nowky;
		for(int i=1;i<=4;i++)
		{
			nowmx=temp.mx,nowmy=temp.my;	
			nowkx=temp.kx+changex[i],nowky=temp.ky+changey[i];
			if(!map[nowkx][nowky])continue;
			if(nowmx==nowkx&&nowmy==nowky)
			{
				nowmx=temp.kx;
				nowmy=temp.ky;
			}
			if(judge[nowmx][nowmy][nowkx][nowky])continue;
			judge[nowmx][nowmy][nowkx][nowky]=1;
			if(nowmx==ex&&nowmy==ey)return temp.dep+1;
			q.push(node{nowmx,nowmy,nowkx,nowky,temp.dep+1});
		}
	}
	return -1;
}
int main(){
	n=getin<int>();m=getin<int>();_=getin<int>();
	int t1,t2,t3;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			map[i][j]=getin<int>();
	while(_--)
	{
		gx=getin<int>();gy=getin<int>();sx=getin<int>();
		sy=getin<int>();ex=getin<int>();ey=getin<int>();
		if(sx==ex&&sy==ey)
		{
			cout<<0<<endl;
			continue;
		}
		getout<long long>(bfs());putchar('\n');
		memset(judge,0,sizeof(judge));
	}
	return 0;
}

AC666纯暴力万岁(bushi

2023/8/8 16:48
加载中...