dfs搜索每个字母对应的数字
剪枝:
1.当一列上三个数a b c都已知时,如果 (a+b)%n!=c && (a+b+1)%n!=c 剪枝(+1是考量进位,注意&&)
2.考虑到我们根据每排数据剪枝的,我们可以改变一下搜索的顺序,按照字母从上往下,从右往左出现的顺序来搜
3.因为我们是从最低位开始搜的,而且,3个数全都是N位,所以高位数组一般较小,低位较大,所以 应该从n-1倒过来搜(高位太大和就不是N位了)
代码:
#include<iostream>
#include<cstdlib>
#include<cstring>
#define Size 30
using namespace std; int n;
int cc[][Size];
int dic[Size]={, ,,,,};
bool vis[Size]; bool row(int i){
if(dic[cc[][i]]!=-&&dic[cc[][i]]!=-&&dic[cc[][i]]!=-){
int k=dic[cc[][i]]+dic[cc[][i]];
if(k%n!=dic[cc[][i]] && (k+)%n!=dic[cc[][i]])return false;
}
return true;
} int next(){
for(int i=;i<=n;i++){
for(int j=;j<;j++){
if(dic[cc[j][i]]==-)return cc[j][i];
}
}
return n+;
} bool check(){
int dd[][Size];
for(int i=;i<;i++){
for(int j=;j<=n;j++){
dd[i][j]=dic[cc[i][j]];
}
}
int f[Size];
memset(f,,sizeof(f));
for(int i=;i<=n;i++){
f[i]+=dd[][i];f[i]+=dd[][i];
while(f[i]>=n)f[i]-=n,f[i+]++;
if(f[i]!=dd[][i])return false;
}
return true;
} void dfs(int k){
if(k>n){
if(check()){
for(int i=;i<=n;i++)cout<<dic[i]<<' ';
exit();
}
}
//jianzhi
for(int i=;i<=n;i++){//
if(!row(i))return;
} for(int i=n-;i>=;i--){
if(!vis[i]){
dic[k]=i;
vis[i]=true;
dfs(next());
vis[i]=false;
dic[k]=-;
}
}
} int main(){
freopen("1064.in","r",stdin);
memset(dic,-,sizeof(dic));
cin>>n;
char temp[Size];
for(int i=;i<;i++){
cin>>temp+;
for(int j=;j<=n;j++){
cc[i][j]=temp[n-j+]-;
}
}
dfs(next());
return ;
}
测试点#alpha1.in 结果:AC 内存使用量: 256kB 时间使用量: 1ms
测试点#alpha10.in 结果:AC 内存使用量: 256kB 时间使用量: 1ms
测试点#alpha2.in 结果:AC 内存使用量: 256kB 时间使用量: 1ms
测试点#alpha3.in 结果:AC 内存使用量: 256kB 时间使用量: 1ms
测试点#alpha4.in 结果:AC 内存使用量: 256kB 时间使用量: 1ms
测试点#alpha5.in 结果:AC 内存使用量: 256kB 时间使用量: 1ms
测试点#alpha6.in 结果:AC 内存使用量: 256kB 时间使用量: 31ms
测试点#alpha7.in 结果:AC 内存使用量: 256kB 时间使用量: 3ms
测试点#alpha8.in 结果:AC 内存使用量: 256kB 时间使用量: 78ms
测试点#alpha9.in 结果:AC 内存使用量: 256kB 时间使用量: 1ms