迷宫

根号分治.

对于队列里面没有满$sqrt(n\ast m\ast h)\{sqrt(n*m*h)\}$的直接对于每个查询进行暴力.

对于满了的,对队列所有的元素做一次$bfs\{bfs\}$,$bfs\{bfs\}$复杂度是$n\ast m\ast h\{n*m*h\}$.

然后清空队列即可.

总复杂度为$nsqrt(n)nsqrt(n)$.

code:

using namespace std;
typedef long long ll;
const int N=5e5+5;
//根号分治. 
int n,m,h,q;
int dis[N];
int dx[6]={1,0,0,-1,0,0};
int dy[6]={0,1,0,0,-1,0};
int dz[6]={0,0,1,0,0,-1};
struct bfs{
	int x,y,z;
};

int f(int X,int Y,int Z)
{
	return (X*m+Y)*h+Z;
}

void run()
{
	queue<bfs>Q;
	vector<bfs>now;
    scanf("%d%d%d%d",&n,&m,&h,&q);
    int base=sqrt(n*m*h);
    memset(dis,0x3f,sizeof dis);
    while(q--)
    {
    	int op,x,y,z;
    	scanf("%d%d%d%d",&op,&x,&y,&z);
    	if(op==1)
    	{
    		Q.push({x,y,z});
    		now.push_back({x,y,z});
		}
		else
		{
			int ans=dis[f(x,y,z)];
			for(auto u:now)
			{
				ans=min(ans,abs(x-u.x)+abs(y-u.y)+abs(z-u.z));
			}
			printf("%d\n",ans);
		}
		if(Q.size()>base)
		{
			for(auto u:now)
			{
				dis[f(u.x,u.y,u.z)]=0;
			}
			now.clear();
			while(Q.size())
			{
				auto u=Q.front();
				Q.pop();
				for(int i=0;i<6;i++)
				{
					bfs st;
					st.x=u.x+dx[i];
					st.y=u.y+dy[i];
					st.z=u.z+dz[i];
					if(st.x<1||st.x>n)	continue;
					if(st.y<1||st.y>m)	continue;
					if(st.z<1||st.z>h)	continue;
					if(dis[f(st.x,st.y,st.z)]>dis[f(u.x,u.y,u.z)]+1)
					{
						Q.push(st);
						dis[f(st.x,st.y,st.z)]=dis[f(u.x,u.y,u.z)]+1;
					}
				}
			}
		}
	}
}

int main()
{
	int T=1;
	cin>>T;
	while(T--)
	{
		run();
	}
	return 0;
}