虫食算
NegaNebulus
2020-07-28 10:27:54
#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 条回复
orz
我来
我先来