22分求调
查看原帖
22分求调
1048193
PengDave楼主2024/7/29 15:26
#include<iostream>
#include<cstring>
using namespace std;
int ans[1000010];
int a[20];
int opt[20][10]={{0},{4,1,2,4,5},
	{3,1,2,3},
	{4,2,3,5,6},
	{3,1,4,7},
	{5,2,4,5,6,8},
	{3,3,6,9},
	{4,4,5,7,8},
	{3,7,8,9},
	{4,5,6,8,9}};
int maxdep=0;
bool vis[5][5][5][5][5][5][5][5][5];
void dfs(int x){
	if(x==maxdep){
		int cnt=0;
		for(int i=1;i<=9;i++){
			if(a[i]%4!=0){
				cnt++;
			}
		}
		if(cnt>5){
			return;
		}
	}
	if(x>maxdep){
		bool re=1;
		for(int i=1;i<=9;i++){
			if(a[i]%4!=0){
				re=0;
				break;
			}
		}
		if(re){
			for(int i=1;i<x;i++){
				cout<<ans[i]<<" ";
			}
			cout<<endl;
			exit(0);
		}
		return;
	}
	for(int i=1;i<=9;i++){
		ans[x]=i;
		for(int j=1;j<=opt[i][0];j++){
			a[opt[i][j]]++;
			a[opt[i][j]]%=4;
		}
		if(!vis[a[1]][a[2]][a[3]][a[4]][a[5]][a[6]][a[7]][a[8]][a[9]]){
			vis[a[1]][a[2]][a[3]][a[4]][a[5]][a[6]][a[7]][a[8]][a[9]]=1; 
			dfs(x+1);
		}
		for(int j=1;j<=opt[i][0];j++){
			a[opt[i][j]]--;
			a[opt[i][j]]=(a[opt[i][j]]+4)%4;
		}
	}
	return;
}
int main(){
	for(int i=1;i<=9;i++){
		cin>>a[i];
		a[i]/=3;
		a[i]%=4;
	}
	for(maxdep=1;;maxdep++){
		memset(vis,0,sizeof(vis));
	    vis[a[1]][a[2]][a[3]][a[4]][a[5]][a[6]][a[7]][a[8]][a[9]]=1;
		dfs(1);
	}
	return 0;
}
2024/7/29 15:26
加载中...