蒟蒻求助!
查看原帖
蒟蒻求助!
173660
zhoukangyang楼主2020/1/29 11:53

大佬们帮帮忙啊 样例都过不了啊 调了55小时了啊

#include<bits/stdc++.h>
using namespace std;
int n,a[8][6],flag,F,d,da[40],db[40],dc[40],ans[8][3],S[12],T;
void cheak() {
	d=0;
	for(int i = 1; i <= 5; i++)
		for(int j = 3; j <= a[0][i]; j++)
			if(a[j][i]==a[j-1][i]&&a[j][i]==a[j-2][i]) {
				++d,da[d]=1,db[d]=j,dc[d]=i;
			}
	for(int i = 3; i <= 5; i++)
		for(int j = 1; j <= a[0][i]; j++)
			if(a[j][i])
				if(a[j][i]==a[j][i-1]&&a[j][i]==a[j][i-2]) {
					++d,da[d]=2,db[d]=j,dc[d]=i;
				}
}
void CD() {
	cheak();
	while(d!=0) {
		for(int i = 1; i <= d; i++) {
			int I=db[i],J=dc[i];
			if(da[i]==1) {
				if(a[I][J]!=0) a[I][J]=0,--a[0][J];
				if(a[I-1][J]!=0) a[I-1][J]=0,--a[0][J];
				if(a[I-2][J]!=0) a[I-2][J]=0,--a[0][J];
			} else {
				if(a[I][J]!=0) a[I][J]=0,--a[0][J];
				if(a[I][J-1]!=0) a[I][J-1]=0,--a[0][J-1];
				if(a[I][J-2]!=0) a[I][J-2]=0,--a[0][J-2];
			}
		}
		for(int i = 1; i <= 5; i++) {
			for(int j = 1; j <= 7; j++) {
				if(!a[j][i]) continue;
				int k=j;
				while(!a[k-1][i]) {
					swap(a[k][i],a[k-1][i]);
					--k;
				}
			}
		}
		cheak();
	}
}
void dfs(int x) {
	if(flag) return;
	if(x==n) {
		F=0;
		for(int i = 1; i <= 5; i++) {
			if(a[0][i]!=0) {
				F=1;
				break;
			}
		}
		if(!F) {
			for(int i = 1; i <= n; i++) {
				printf("%d %d %d\n",ans[i][0],ans[i][1],ans[i][2]);
			}
			flag=1;
		}
		return;
	}
	for(int i = 1; i <= T; i++) S[i]=0;
	for(int i = 1; i <= 5; i++)
		for(int j = 1; j <= a[0][i]; j++)
			S[a[j][i]]++;
	for(int i = 1; i <= T; i++)
		if(S[i]==1|S[i]==2)
			return;
	int gc[8][6];
	for(int i = 1; i <= 5; i++) {
		gc[0][i]=a[0][i];
		for(int j = 1; j <= a[0][i]; j++)
			gc[j][i]=a[j][i];
	}
	for(int i = 1; i <= 5; i++) {
		for(int j = 1; j <= a[0][i]; j++) {
			if(i!=5) {
				if(a[j][i+1]) swap(a[j][i+1],a[j][i]);
				else {
					++a[0][i+1],a[a[0][i+1]][i+1]=a[j][i];
					for(int k = j+1; k <= a[0][i]; k++)
						a[k-1][i]=a[k][i];
					a[a[0][i]][i]=0,--a[0][i];
				}
				CD();
				ans[x+1][0]=j-1,ans[x+1][1]=i-1,ans[x+1][2]=1;
				dfs(x+1);
				for(int i = 1; i <= 5; i++) {
					a[0][i]=gc[0][i];
					for(int j = 1; j <= gc[0][i]; j++)
						a[j][i]=gc[j][i];
				}
			}
			if(i!=1) {
				if(a[j][i-1]) continue;
				++a[0][i-1],a[a[0][i-1]][i-1]=a[j][i];
				for(int k = j+1; k <= a[0][i]; k++)
					a[k-1][i]=a[k][i];
				a[a[0][i]][i]=0,--a[0][i];
				CD();
				ans[x+1][0]=j-1,ans[x+1][1]=i-1,ans[x+1][2]=-1;
				dfs(x+1);
				for(int i = 1; i <= 5; i++) {
					a[0][i]=gc[0][i];
					for(int j = 1; j <= gc[0][i]; j++)
						a[j][i]=gc[j][i];
				}
			}
		}
	}
}
int main() {
	scanf("%d",&n);
	for(int i = 1; i <= 5; i++) {
		for(int j = 1; j <= 8; j++) {
			scanf("%d",&a[j][i]);
			T=max(T,a[j][i]);
			if(a[j][i]==0) {
				a[0][i]=j-1;
				break;
			}
		}
	}
	dfs(0);
	if(!flag) printf("-1");
	return 0;
}
2020/1/29 11:53
加载中...