$(>_^)$

NegaNebulus 2020-07-28 14:25:56 2020-07-28 15:34:11

#include<bits/stdc++.h>
using namespace std;
int n;
char a[4][27];
int num[27];
bool use[27]={false};

int ltn(char py)//字母转数字 
{
	return py-'A'+1;
}

void dfs(int hor,int ver,int ah)
{
	if(hor==0){   //已经搜完 
		if(ah==0){  //进位必须为 0 
			for(int i=1;i<=n;i++)
				cout<<num[i]<<" ";  //输出 
			exit(0);  //结束 
		}
	}
	for(int i=hor-1;i>=1;i--){   //剪枝 1,已赋值情况下判断 
		int w1=num[ltn(a[1][i])],w2=num[ltn(a[2][i])],w3=num[ltn(a[3][i])];//一列三数 
		if(w1==-1||w2==-1||w3==-1)//未赋值则跳过 
			continue;
		if((w1+w2)%n!=w3&&(w1+w2+1)%n!=w3)  //判断 
			return;
	}
	//搜索部分↓↓↓↓↓↓ 
	if (num[ltn(a[ver][hor])]==-1){ //如果这个位置上还没被赋值,就进行赋值操作 
        for(int i=n-1;i>=0;i--){ //枚举从n-1到0,倒着枚举更快 
            if(!use[i]){ //如果这个数没有用过 
                if(ver!=3){//不是最后一行
                    num[ltn(a[ver][hor])]=i;//就将这个位置赋上值 
                    use[i]=true;//标记这个数用过 
                    dfs(hor,ver+1,ah);//继续搜索下一行 
                    num[ltn(a[ver][hor])]=-1; //还原↓下同 
                    use[i]=false;
                }
                else{//最后一行 
                    int w=num[ltn(a[1][hor])]+num[ltn(a[2][hor])]+ah;//两个数加上它们的进位 
                    if(w%n!=i)//不是这个数则跳过 
                        continue;
                    use[i]=1;num[ltn(a[3][hor])]=i;//赋值,标记这个数用过 
                    dfs(hor-1,1,w/n);//搜索下一列,进位需要改变 
                    use[i]=false;//还原↓下同 
					num[ltn(a[3][hor])]=-1; 
                }
            }
        }
    }else{ //如果这个位置上已经被赋值了 
        if (ver!=3) //继续搜索 
            dfs(hor,ver+1,ah);
        else //最后一行 
        {
            int w=num[ltn(a[1][hor])]+num[ltn(a[2][hor])]+ah;//同上 
            if (w%n!=num[ltn(a[3][hor])]) //剪枝 2 ,赋值错误则返回 
                return;
            dfs(hor-1,1,w/n);//搜索下一列,进位需要改变 
        }
    }
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); 
	cin>>n;
	for(int i=1;i<=3;i++){
		for(int j=1;j<=n;j++){
			cin>>a[i][j];
		}
	}
	memset(num,-1,sizeof(num));//全赋值为-1 表示未使用 
	dfs(n,1,0);
	return 0;
}

共 3 条回复

810816659

TQL^{TQL^{TQL}_{TQL}}_{TQL^{TQL}_{TQL}}

xy0313

tql ^ {tql}

NegaNebulus

我先来

{菜^{菜^{菜^{菜^{菜^{菜^{菜^{菜^{菜^{菜^{菜^菜}}}}}}}}}}}