玄关
查看原帖
玄关
1294410
yuruilin2026楼主2025/2/6 17:36
#include <bits/stdc++.h>
using namespace std;
int n = 8,mp1[10][10],mp2[10][10];
int fx[5] = {0,1,0,-1,0},fy[5] = {0,0,1,0,-1};
bool vis1[9][9][9][9][9][9][9][9];
bool vis2[9][9][9][9][9][9][9][9];
struct ppp{
	int x;
	int y;
}a[6],b[6];
bool cmp(ppp p1,ppp p2){
	if(p1.x == p2.x) return p1.y < p2.y;
	return p1.x < p2.x;
}
void sou1(int step){
	if(step >= 5) return;
	ppp c[6] = {};
	int cnt = 0;
	for(int i = 1;i <= 8;++i){
		for(int j = 1;j <= 8;++j){
			if(mp1[i][j] == 1){
				c[++cnt].x = i;
				c[cnt].y = j;
			}
		}
	}
	if(vis1[c[1].x][c[1].y][c[2].x][c[2].y][c[3].x][c[3].y][c[4].x][c[4].y] == 1) return;
	for(int i = 1;i <= 4;++i){
		for(int j = 1;j <= 4;++j){
			if(i == j) continue;
			for(int k = 1;k<= 4;++k){
				if(i == k || j == k) continue;
				for(int l = 1;l <= 4;++l){
					if(i == l || j == l || k == l) continue;
					vis1[c[i].x][c[i].y][c[j].x][c[j].y][c[k].x][c[k].y][c[l].x][c[l].y] = 1;
				}
			}
		}
	}
	for(int i = 1;i <= 4;++i){
		for(int j = 1;j <= 4;++j){
			int xx = c[i].x + fx[j],yy = c[i].y + fy[j];
			if(xx <= 0 || xx >= 9 || yy <= 0 || yy >= 9){
				continue;
			} 
			if(mp1[xx][yy] == 0){
				swap(mp1[xx][yy],mp1[c[i].x][c[i].y]);
				sou1(step+1);
				swap(mp1[xx][yy],mp1[c[i].x][c[i].y]);
			}
			else if(mp1[xx+fx[j]][yy+fy[j]] == 0 && xx+fx[j] >= 1 && xx+fx[j] <= 8 && yy+fy[j] >= 1 && yy+fy[j] <= 8){
				swap(mp1[xx+fx[j]][yy+fy[j]],mp1[c[i].x][c[i].y]);
				sou1(step+1);
				swap(mp1[xx+fx[j]][yy+fy[j]],mp1[c[i].x][c[i].y]);
			}
		}
	}
	return;
}
bool sou2(int step){
	if(step >= 5) return 0;
	ppp c[6];
	int cnt = 0;
	for(int i = 1;i <= 8;++i){
		for(int j = 1;j <= 8;++j){
			if(mp2[i][j] == 1){
				c[++cnt].x = i;
				c[cnt].y = j;
			}
		}
	}
	//if(cnt != 4) return 0;
	if(vis2[c[1].x][c[1].y][c[2].x][c[2].y][c[3].x][c[3].y][c[4].x][c[4].y] == 1) return 0;
	for(int i = 1;i <= 4;++i){
		for(int j = 1;j <= 4;++j){
			if(i == j) continue;
			for(int k = 1;k <= 4;++k){
				if(i == k || j == k) continue;
				for(int l = 1;l <= 4;++l){
					if(i == l || j == l || k == l) continue;
					vis2[c[i].x][c[i].y][c[j].x][c[j].y][c[k].x][c[k].y][c[l].x][c[l].y] = 1;
				}
			}
		}
	}
	if(vis1[c[1].x][c[1].y][c[2].x][c[2].y][c[3].x][c[3].y][c[4].x][c[4].y] == 1){
		return 1;
	}
	for(int i = 1;i <= 4;++i){
		for(int j = 1;j <= 4;++j){
			int xx = c[i].x + fx[j],yy = c[i].y + fy[j];
			if(xx <= 0 || xx >= 9 || yy <= 0 || yy >= 9){
				continue;
			} 
			if(mp2[xx][yy] == 0){
				swap(mp2[xx][yy],mp2[c[i].x][c[i].y]);
				if(sou2(step+1)){
					swap(mp2[xx][yy],mp2[c[i].x][c[i].y]);
					return 1;
				}
				swap(mp2[xx][yy],mp2[c[i].x][c[i].y]);
			}
			else if(mp2[xx+fx[j]][yy+fy[j]] == 0 && xx+fx[j] >= 1 && xx+fx[j] <= 8 && yy+fy[j] >= 1 && yy+fy[j] <= 8){
				swap(mp2[xx+fx[j]][yy+fy[j]],mp2[c[i].x][c[i].y]);
				if(sou2(step+1)){
					swap(mp2[xx+fx[j]][yy+fy[j]],mp2[c[i].x][c[i].y]);
					return 1;
				}
				swap(mp2[xx+fx[j]][yy+fy[j]],mp2[c[i].x][c[i].y]);
			}
		}
	}
	return 0;
}
int main(){
	cin.tie(0),cout.tie(0);
	while(1){
		memset(vis1,0,sizeof(vis1));
		memset(vis2,0,sizeof(vis2));
		memset(mp1,0,sizeof(mp1));
		memset(mp2,0,sizeof(mp2));
		for(int i = 1;i <= 4;i++){
			if(!(cin >> a[i].x && cin >> a[i].y)) return 0;
			mp1[a[i].x][a[i].y] = 1;
		}
		for(int i = 1;i <= 4;i++){
			cin >> b[i].x >> b[i].y;
			mp2[b[i].x][b[i].y] = 1;
		}
		sou1(0);
		if(sou2(0) == 0){
			cout << "NO" << endl;
		}
		else{
			cout << "YES" << endl; 
		}
	}
	return 0;
}
2025/2/6 17:36
加载中...