「一本通 1.4 例 3」Knight Moves -- 双向bfs

Luogu 10028

题目分析：

• 每次选队列中节点数少的扩展，注意清空
• 把$x打成y，调了很久$x打成y，调了很久

Code:

#include <bits/stdc++.h>
using namespace std;
#define maxn 310

int ans,T,n,s_x,s_y,t_x,t_y,d[3][maxn][maxn];
int dx[]={2,2,1,1,-1,-1,-2,-2};
int dy[]={1,-1,2,-2,2,-2,1,-1};
bool vis[3][maxn][maxn];
struct node {
	int x,y;
};
queue <node> q[2];

inline int read_() {
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9') {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9') {
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x*f;
}

inline bool expand_(int k) {
	node pdc=q[k].front();
	q[k].pop();
	int x=pdc.x,y=pdc.y;
	for(int i=0;i<8;++i) {
		int px=x+dx[i];
		int py=y+dy[i];
		if(px<0||py<0||px>=n||py>=n) continue;
		if(vis[k][px][py]) continue;
		d[k][px][py]=d[k][x][y]+1;
		vis[k][px][py]=true;
		if(vis[k^1][px][py]) {
			ans=d[k][px][py]+d[k^1][px][py];
			return true;
		}
		q[k].push( (node) {px,py} ); 
	}
	return false;
}

inline void bfs_() {
	while(!q[0].empty()) q[0].pop();
	while(!q[1].empty()) q[1].pop();
	q[0].push( (node) {s_x,s_y} );
	vis[0][s_x][s_y]=1;d[0][s_x][s_y]=0;
	q[1].push( (node) {t_x,t_y} );
	vis[1][t_x][t_y]=1;d[1][t_x][t_y]=0;
	while(!q[0].empty()||!q[1].empty()) {
		if(q[0].empty()) {
			if(expand_(1)) return ;
			continue;
		}
		if(q[1].empty()) {
			if(expand_(0)) return ;
			continue;
		}
 		if(q[0].size()<q[1].size()) {
			if(expand_(0)) return ;
		}
		else {
			if(expand_(1)) return ;
		}
	}
}

void readda_() {
	T=read_();
	while(T--) {
		n=read_();
		s_x=read_();s_y=read_();
		t_x=read_();t_y=read_();
		if(s_x==t_x&&s_y==t_y) {
			printf("0\n");
			continue;
		}
		memset(vis,0,sizeof(vis));
		memset(d,0,sizeof(d));
		bfs_();
		printf("%d\n",ans);
	}
}

int main() {
	freopen("a.txt","r",stdin);
	readda_();
	return 0;
}