1. 时间复杂度分析

• 状态空间计算：

  • 有 $4$ 个棋子，每个棋子的最大可能转移情况是 $4$ 种。
  • 每一步最多产生 $16$ 个新状态（因为 $4 \times 4 = 16$）。
  • 计算 $8$ 步后的总状态数为 $16^8$，即 $(2^4)^8 = 2^{32}$。

• 直接 BFS 的问题：

  • 直接广度优先搜索（BFS）需要遍历 $2^{32}$ 种状态，必然超时。

2. 双向广搜优化

(1) 核心思路

• 双向搜索：
  • 从初态正向 BFS $4$ 步，生成状态集 $A$。
  • 从终态逆向 BFS $4$ 步，生成状态集 $B$。
  • 若 $A \cap B \neq \emptyset$，则存在可行解。

(2) 正确性证明

• 路径等价性：
  • 假设存在一条路径：初态 $\xrightarrow{6 \text{步}} C \xleftarrow{2 \text{步}} \text{终态}$。
  • 等价于：初态 $\xrightarrow{4 \text{步}} D \xleftarrow{4 \text{步}} \text{终态}$。
    • 通过逆向操作，终态的 $2$ 步可转换为初态的逆向 $2$ 步（对称性）。
    • 因此总步数仍为 $8$ 步，但状态空间缩减为 $2 \times 16^4 = 2 \times 2^{16} = 2^{17}$。

(3) 复杂度对比

3. 关键问题解答

为什么划分成两个 $4$ 步可行？

• 对称性原理：任何 $k$ 步正向操作均可转换为 $k$ 步逆向操作。
  • 若存在 $6+2$ 步的解，则必然存在 $4+4$ 步的解（通过调整对称路径）。
• 数学表达：
  • 设正向路径为 $S \to C$（$6$ 步），逆向路径为 $T \to C$（$2$ 步）。
  • 则 $S \to C$ 的前 $4$ 步与 $T \to C \to S_4$（逆向 $4$ 步）必然在中间状态 $D$ 相交。

4. 实现建议

1. 状态表示：使用哈希或位压缩存储棋盘状态。
2. 终止条件：当两个方向的搜索层出现交集时立即返回。
3. 优化技巧：
   • 优先扩展状态数较少的方向。
   • 使用预处理减少重复计算。

5. 总结

• 双向广搜将指数级复杂度 $O(2^{32})$ 降为 $O(2^{17})$，效率提升 $2^{15}$ 倍。
• 正确性依赖于路径对称性和状态空间的覆盖性。

#include <cstdio>
#include <set>
#include <queue>
#include <cstring>
#include <algorithm>
#define fi first
#define se second
#define pii pair<int,int>
using namespace std;
typedef long long LL;
const int maxn = 1e3+5;

int moved[4][2] = {{1,0}, {0,-1}, {-1,0}, {0,1}};
set<LL> s1, s2;
queue<LL> Q;

// 输入点，并将二维转化为一维 
void input(LL &a){
	int x,y;
	scanf("%d%d",&x,&y);
	--x; --y;
	int z = x*8 + y;
	a |= (1LL << z);
}
// 检查点是否在棋盘内 
bool check(int x, int y){
	if(x >= 0&&x < 8&&y >= 0&&y < 8) return true;
	return false;
}
// 清空队列 
void clear_que(queue<LL> &Q){
	queue<LL> empty;
	swap(Q, empty);
}

// 当前棋盘s, 扩展层数cnt，从起点开始扩展过(正向bfs)的点s1，从终点扩展过的点(反向bfs)的点s2，sec:是否是第二次bfs(反向bfs) 
// 返回是否找到交点 
bool expand(LL s, int &next_layer, set<LL> &ss1, set<LL> &ss2, bool sec){
	
	// 根据s找到4个点 
	bool exists[10][10]; 	//棋盘上(x,y)是否是点
	memset(exists, 0, sizeof(exists));
	int P[5][2]; 		// 记录棋盘上的4个点
	int cnt = 0; 
	for(int i = 0; i < 64; ++i){
		if(s&(1LL << i)){ //找到一个点 
			int x = i/8;
			int y = i%8;
			exists[x][y] = 1;
			P[cnt][0] = x;
			P[cnt++][1] = y;
		}
	}
	
	// 依次扩展
	for(int i = 0; i < 4; ++i){
		
		int x = P[i][0], y = P[i][1];
		int z = x*8 + y;
		LL t = s - (1LL << z);
		LL next_state;
		
		for(int j = 0; j < 4; ++j){ // 4个方向
			next_state = t;
			int x2 = x + moved[j][0];
			int y2 = y + moved[j][1];
			if(check(x2, y2)&&exists[x2][y2]){ //有邻居，可以跳一格 
				x2+= moved[j][0];
				y2+= moved[j][1];
			}
			
			if(!check(x2,y2)||exists[x2][y2]) continue; //若该位置不在棋盘或已经有棋子
			z = x2*8 + y2;
			next_state += (1LL << z);
			
			if(!ss1.count(next_state)){
				if(sec && ss2.count(next_state)) return true; // 如果是反向搜索且有交点了，找到解
				Q.push(next_state);
				//if(sec) printf("22222: ");
				//else printf("111111: ");
				//printf("%d,%d\n", x2+1,y2+1);
				//printf("%lld\n",next_state);
				ss1.insert(next_state);
				++next_layer; 
			}
		}
	} 
	return false;
}

bool bfs(LL s, set<LL> &ss1, set<LL> &ss2, bool sec){
	
	clear_que(Q);
	Q.push(s);
	ss1.clear();
	ss1.insert(s);
	int cnt = 0; // 当前扩展层数
	int next_layer; // 下一层点的个数
	int cur_layer = 1; //当前层中点的个数 
	while(cnt < 4){
		next_layer = 0;
		while(cur_layer > 0){
			LL t = Q.front(); Q.pop(); --cur_layer;
			bool ans = expand(t, next_layer, ss1, ss2, sec);
			if(ans) return true;
		}
		//printf("next is %d\n",next_layer);
		cur_layer = next_layer;
		//printf("cur id %d\n",cur_layer);
		++cnt;
	}
	return false;
}

bool solve(LL s, LL e){ //这里写的int导致一直错，太不小心了
	bfs(s, s1, s2, false); // 正向搜
	return bfs(e, s2, s1, true); // 反向搜 
}

int main()
{
	//freopen("in.txt","r",stdin);
	int x,y;
	LL s,e;
	while(scanf("%d%d",&x,&y) == 2){
		s = e = 0;
		--x; --y;
		int z = x*8 + y;	//二维变一维
		s |= (1LL << z); 
		for(int i = 1; i < 4; ++i) input(s);
		for(int i = 0; i < 4; ++i) input(e);
		
		//printf("input ok");
		bool ans = solve(s, e);
		if(ans) printf("YES\n");
		else printf("NO\n");
	}

	return 0;
}